Results 1 to 2 of 2

Math Help - u, v-path

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    30

    u, v-path

    Prove that if a graph G has exactly two vertices u and v of odd degree, then G has a u, v-path.

    I began my proof assuming to the contrary that G does not have a u, v-path, but I'm having trouble figuring out how to show this isn't possible.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by meggnog View Post
    Prove that if a graph G has exactly two vertices u and v of odd degree, then G has a u, v-path.
    Do you know that a component of a graph is a maximally connected subgraph? Is it possible for the two odd vertices to be in different components?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Path integral
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 8th 2010, 01:34 PM
  2. sketch this path
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: November 30th 2009, 11:11 AM
  3. path from the vertex ??
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 8th 2009, 07:44 PM
  4. degree of a path, path homotopy.
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 19th 2009, 05:37 PM
  5. is this set path-connected
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 2nd 2008, 07:47 AM

Search Tags


/mathhelpforum @mathhelpforum