Thread: 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?

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, such that
Because the graph is connected then there is a path .
If or or we are done.
Can you argue that one of those three must be true?

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.