Triangle-free graphs with three common neighbours
ID: triangle-free-graphs-with-three-common-neighbours
For a finite simple graph with at least two vertices, no triangles, and exactly three common neighbours for every nonadjacent pair, the graph is connected. For adjacent vertices , the bipartite graph between and has degree two at every vertex, forcing . Thus the graph is regular. Counting second neighbours gives . The nontrivial adjacency eigenvalues are , and the larger-root multiplicity is . Integrality forces to be an odd integer dividing , yielding the stated degrees. The complete bipartite graph realizes degree three. The one-vertex graph is a vacuous exception with degree zero.
New to topics? Read the docs here!