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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: