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
    Now I get a proof. The idea is to show each pair of adjacent vertices has the same degree.(The proof does not need the triangle free condition)2012-05-03
  • 0
    The proof is for regularity, but for strongly regularity I have not found any counterexample so far, does the triangle-free condition play any role in this context?2012-05-03
  • 0
    For the benefit of other users, and to get this question off the unanswered list, you could submit your proof of regularity as an answer. Answering your own questions is encouraged.2012-05-03
  • 0
    I can't answer my own question within 8 hours of asking~I will soon it allows me to do so.2012-05-04
  • 0
    The title doesn't correspond to the question.2012-05-04
  • 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