Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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) – Harry May 3 '12 at 23:25
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? – Harry May 3 '12 at 23:37
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. – Brian M. Scott May 3 '12 at 23:44
I can't answer my own question within 8 hours of asking~I will soon it allows me to do so. – Harry May 4 '12 at 1:21
The title doesn't correspond to the question. – joriki May 4 '12 at 14:18

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$.

share|cite|improve this answer
$Q_n$ (for $n > 2$) does not fullfil the requirement that any two vertices with a common neighbor have exactly 2 common neighbors. Look at the drawing of $Q_3$ here: The vertex in the lower left and the upper right have exactly one common neighbor. – utdiscant Jul 8 '12 at 6:06
Actually, it seems the drawing on Wikipedia which I referred too is wrong. – utdiscant Jul 8 '12 at 6:18
@utdiscant: You're right; I fixed the Wikipedia image. – joriki Jul 8 '12 at 7:03

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.