I need to show that if $G$ is a graph such that every pair of vertices have exactly two neighbors in common, then $G$ is regular, and express the number of vertices in terms of its regularity.

Take any $v_1, v_2\in V(G)$ that are adjacent. Let $w_1\in N(v_1)$, then $w_1$ and $v_2$ share two common neighbors, one of which is $v_1$, the other one is $w_2$.

Case 1: $w_1$ and $v_2$ are adjacent.

Case 2: If $w_1$ and $v_2$ are not adjacent, then $w_1$ is not a common vertex of $v_1$ and $v_2$, so there must be at least one vertex $w_3\notin\{w_1,w_2\}$ that is adjacent to both $v_1$ and $v_2$.

In all cases, every neighbor of $v_1$ induces an edge incident to $v_2$, so $deg(v_2)\geq deg(v_1)$. By symmetry $deg(v_1)\geq deg(v_2)$, and by connectedness, $G$ is regular.

But how is regularity related to the total number of vertices?

  • 1
    $\begingroup$ The only relation that immediately comes to mind is $|V|r/2=|E|$ where $r$ is the regularity. Not sure if anything else could come out of regularity though. $\endgroup$ – Μάρκος Καραμέρης May 27 '18 at 14:11
  • 1
    $\begingroup$ Google finds this relevant paper $\endgroup$ – Rob Arthan May 27 '18 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.