Results 1 to 3 of 3

Math Help - one more graph theory

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,707
    Thanks
    1637
    Awards
    1
    Quote Originally Posted by zhupolongjoe View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum