# A graph with n points satisfies some conditions. [duplicate]

This question already has an answer here:

(APMO 1990) Let $$G$$ is a graph that satisfies the following conditions. (1) No point has edges to all other points, (2) there are no triangles, (3) given any two points $$A,B$$ s.t. there is no edge AB, there is exactly one point $$C$$ that there are edges AC and BC. Prove every point has the same degree.

I found a proof online, but it uses common complement, which doesn't make sense to me. I've tried considering the $$N_a,N_b$$ of two points A, B, where there isn't an edge $$AB$$ and proving them having no edges between $$N_a,N_b$$ without, and their common point $$C$$, but then I'm stuck.

## marked as duplicate by Santana Afton, YuiTo Cheng, José Carlos Santos, Parcly Taxel, CesareoMay 26 at 11:05

Note that we cannot have a cycle of four vertices by condition 3 (which requires there to be exactly one vertex connected to any two). Consider a vertex $$v$$ and its $$k$$ neighbours $$v_1, v_2, \ldots v_k$$. Take some vertex $$w$$ not adjacent to $$v$$. If $$w$$ and $$v_i$$ are adjacent then we let $$w_i=v_i$$. Otherwise, let the common neighbour of $$w$$ and $$v_i$$ be $$w_i$$. Note that $$w_i$$ is not any $$v_j$$ by condition 2. Furthermore, if $$w_i = w_j$$, then the vertices $$v_i, v_j, v, w_i = w_j$$ form a 4-cycle, which is impossible, or they form a triangle, which is just as bad. So all $$w_i$$ are distinct and so $$w$$ has degree at least $$k$$. So $$\deg (w) \geq \deg (v)$$, and by symmetry we obtain the reverse inequality, so the degrees are equal.
Now every vertex apart from the one common vertex of $$v$$ and $$w$$ is not connected to one of these two and so has the same degree as them. So all vertices except one have the same degree, but since this last vertex is not connected to some vertex, it also has the same degree.
• How do you know $w$ and $v_i$ have a common neighbour? Why can't $w$ be adjacent to $v_i$? – bof May 25 at 6:04
• Actually, such graphs do exist; one example is the $5$-cycle. The proof that such graphs cannot exist assumes a stronger hypothesis: that any two vertices, even adjacent ones, have exactly one common neighbor. – Misha Lavrov May 25 at 10:54