Let $G$ be a triangle-free simple $n$-vertex graph such that every pair of non-adjacent vertices has exactly two common neighbors. Prove that $n(G) = 1 + \binom{d(x)+1}{2}$, where $x \in V(G)$. Hence, conclude that $G$ is regular.

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4

Solution

1. Choose any vertex $x$ in $G$. $x$ has $d(x)$ neighbors, and let them be $v_1, v_2, \dots, v_{d(x)}$, where $d(x)$ is the degree of $x$.

2. Since $G$ does not have triangles, there are no edges between $v_1, v_2, \dots, v_{d(x)}$.

3. The number of vertices non-adjacent to $x$ is $n - d(x) - 1$.

• This is calculated as: (Total number of vertices in $G$) - (the number of neighbors of $x$) - ($x$ itself).
• Let $w$ be one of these non-adjacent vertices.

4. Since every pair of non-adjacent vertices has exactly two common neighbors and there are no triangles in $G$, $w$ is adjacent to exactly two vertices among $v_1, v_2, \dots, v_{d(x)}$. This situation applies to all $n - d(x) - 1$ non-adjacent vertices.

5. Each of the $n - d(x) - 1$ vertices has exactly two common neighbors among $v_1, v_2, \dots, v_{d(x)}$. Thus,
$$n - d(x) - 1 = \binom{d(x)}{2}.$$

6. Simplifying the equation:
$$n - d(x) - 1 = \frac{d(x)(d(x) - 1)}{2},$$
$$\Rightarrow n = \frac{d(x)(d(x) + 1)}{2} + 1,$$
$$\Rightarrow n = \binom{d(x) + 1}{2} + 1.$$

7. The above equation shows that $n(G)$ only depends on $d(x)$. Thus, every vertex in $G$ has the same degree $d(x)$.

• Therefore, $G$ is a regular graph.