**Problem 1J: Let **** be a simple graph on **** vertices **** with no vertex of degree **** Suppose that for any two vertices of ****, there is a unique vertex joined to both of them.**

**(i) If **** and **** are not adjacent, prove that they have the same degree.**

**(ii) Now Show that **** is a regular graph.**

**Solution: **

(i) First, there is a unique vertex joined to and Suppose the neighbors of except are , then there is a unique vertex joining both and Now we show that , if . Otherwise suppose then there are two vertices, and , joined to and , a contradiction. So there is a one to one correspondence between the neighbors of and those of , except vertex 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 , there exist two vertices that are not adjacent, thus have the same degree by (i). Suppose the degree of them is . There is a unique vertex joined to and , and any other vertex is either not adjacent to or , so the degree of them are all At last, since the degree of vertex is still at most , there exists some vertex of degree that is not adjacent to , thus the degree of is too. Then 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.

### Like this:

Like Loading...

*Related*