4
$\begingroup$

If $G$ is a connected finite graph which has no triangles, and $G$ has the property that if two vertices have a common neighbour then they have exactly two common neighbours, does $G$ have to be strongly regular?

Note: I showed it is regular, but how to prove/disprove it's strongly regular?

  • 0
    Any strongly regular graph with no triangles, is a $srg(n,k,0,\mu)$, and according to http://en.wikipedia.org/wiki/Strongly_regular_graph#Examples there is only 7 examples of such graphs. Since you require $\mu$ to be either 0 or 2, the only two examples left are the Gewirtz Graph, and the Clebsch Graph.2012-07-08

2 Answers 2

1

The answer is "no". A counterexample is provided by the hypercube graph $Q_n$ for any $n\gt2$, in particular by the nearest-neighbour graph of the corners of a cube. The conditions are fulfilled, but some non-adjacent vertices have $2$ common neighbours while others have $0$.

  • 0
    @utdiscant: You'$r$e $r$ight; I fixed the Wikipedia image.2012-07-08
0

Let u, v be two adjacent vertices. let v' be a neighbour of v distinct from u, then u and v' has common neighbour v, by the condition there must exists another vertex u' wihch is adjacent to both u and v'. So repeat this argument to each neighbour of v (distinct from u) to get deg(u) is not less than deg(v). By symmetry of u and v to get the other direction.