## Problem1J

Problem 1J: Let ${G}$ be a simple graph on ${n}$ vertices ${(n>3)}$ with no vertex of degree ${n-1.}$ Suppose that for any two vertices of ${G}$, there is a unique vertex joined to both of them.

(i) If ${x}$ and ${y}$ are not adjacent, prove that they have the same degree.

(ii) Now Show that ${G}$ is a regular graph.

Solution:

(i) First, there is a unique vertex ${u}$ joined to ${x}$ and ${y.}$ Suppose the neighbors of ${x}$ except ${u}$ are ${x_{1},x_{2},\ldots ,x_{k}}$, then there is a unique vertex ${y_{i}}$ joining both ${x_{i}}$ and ${y.}$ Now we show that ${ y_{i}\neq y_{j}}$, if ${i\neq j}$. Otherwise suppose ${y_{i}=y_{j},}$ then there are two vertices, ${y_{i}}$ and ${x}$, joined to ${x_{i}}$ and ${x_{j}}$, a contradiction. So there is a one to one correspondence between the neighbors of ${x}$ and those of ${y}$, except vertex ${u}$ which joined to both of them. Therefore two vertices have the same degree if they are not adjacent.

(ii) Since the degree of any vertex is at most ${n-2}$, there exist two vertices ${v_{1},v_{2}}$ that are not adjacent, thus have the same degree by (i). Suppose the degree of them is ${d}$. There is a unique vertex ${w}$ joined to ${v_{1}}$ and ${v_{2}}$, and any other vertex is either not adjacent to ${v_{1} }$ or ${v_{2}}$, so the degree of them are all ${d.}$ At last, since the degree of vertex ${w}$ is still at most ${n-2}$, there exists some vertex of degree ${d}$ that is not adjacent to ${w}$, thus the degree of ${w}$ is ${d}$ too. Then ${G}$ is a regular graph.

Note: It is quite interesting to see that how to deduce properties of graph from some assumptions of graph. To do research, we usually add conditions to deduce some properties if the problem is too hard to attack directly.