# one more graph theory

• Sep 23rd 2009, 08:57 AM
zhupolongjoe
one more graph theory
Show that if G is a connected graph that is not regular, then G contains adjacent vertices u and v such that deg u=/= deg v.

This seems too obvious to require a proof. Isn't it just be the definition of a regular graph. So we could assume G contains only adjacent vertices u and v such that deg u=deg v. Then G is, by definition regular.

Or is it something else?
• Sep 23rd 2009, 10:16 AM
Plato
Quote:

Originally Posted by zhupolongjoe
Show that if G is a connected graph that is not regular, then G contains adjacent vertices u and v such that deg u=/= deg v?

Because the graph is not regular, there are two vertices, $u~\&~v$ such that $\text{deg}(u)\ne\text{v}$
Because the graph is connected then there is a path $u - u_1 - u_2 \cdots - u_n - v$.
If $\text{deg}(u)\ne\text{deg}{(u_1)}$ or $\text{deg}(u_k)\ne\text{deg}{(u_{k+1})}$ or $\text{deg}(u_n)\ne\text{deg}{(v)}$ we are done.
Can you argue that one of those three must be true?
• Sep 23rd 2009, 11:02 AM
zhupolongjoe
Thanks.

Well is it because if we assumed none of those were true, then clearly all the degrees would be equal and the graph would then be regular...a contradiction.