0
$\begingroup$

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

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.

Interestingly, such a graph described in the question cannot exist. See this paper for a proof: http://math.mit.edu/~fox/MAT307-lecture20.pdf

$\endgroup$
  • $\begingroup$ How do you know $w$ and $v_i$ have a common neighbour? Why can't $w$ be adjacent to $v_i$? $\endgroup$ – bof May 25 at 6:04
  • $\begingroup$ For the absence of four-cycles, you also need condition 2. Condition 3 alone would allow four-cycles as long as both diagonals are edges $\endgroup$ – Hagen von Eitzen May 25 at 6:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Misha Lavrov May 25 at 10:54
  • $\begingroup$ @MishaLavrov I believe Hagen is saying that you need the “no triangles” condition to ban four-cycles — the “unique mutual friend” condition isn’t enough. Also, as to your comment about the existence of such graphs, this answer (on a question for which this one is a duplicate) shows that, possibly, only four unique graphs satisfy these hypothesis. Interesting! $\endgroup$ – Santana Afton May 25 at 13:31

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