Results 1 to 6 of 6

Math Help - Explain why, in ANY graph, there must be an even number of odd vertices...

  1. #1
    Member
    Joined
    Nov 2006
    Posts
    126

    Explain why, in ANY graph, there must be an even number of odd vertices...

    How would I go about explaining this please?

    Thanks guys!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by anthmoo View Post
    How would I go about explaining this please?
    Becuase the sum of the edge is a formula,
     2|E|=\sum_{v\in V}d(v)
    The summation formula means the sum of all degrees of verticies.
    Sine the left hand side is even thus is the right.
    Thus, the sum of all degrees is always even.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2006
    Posts
    126
    Quote Originally Posted by ThePerfectHacker View Post
    Becuase the sum of the edge is a formula,
     2|E|=\sum_{v\in V}d(v)
    The summation formula means the sum of all degrees of verticies.
    Sine the left hand side is even thus is the right.
    Thus, the sum of all degrees is always even.
    All degrees? I was just asking about the sum of degrees of odd nodes, not the sum off all degrees of nodes.
    Last edited by anthmoo; January 14th 2007 at 10:06 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1
    Quote Originally Posted by anthmoo View Post
    All degrees? I was just asking about the sum of degrees of odd nodes, not the sum off all degrees of nodes.
    If one adds any collection of integers and the resulting sum is even then that collection must contain an even number of odd integers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,914
    Thanks
    779
    Hello, anthmoo!

    Here is a primitive approach . . . almost an inductive proof.


    Explain why, in ANY graph, there must be an even number of odd vertices.

    Let's say we have a graph with n vertices (some even, some odd)
    . . and the parity (evenness or oddness) of each vertex is noted.
    Let's say that there are E even vertices and O odd vertices.


    Now add another vertex X to the graph.

    If X is not connected to any of the n vertices,
    . . it remains a 0-vertex (even).
    The number of even vertices increases by one,
    . . but the number of odd vertices does not change.


    If X is connected to any of the n vertices, there are two outcomes.

    (a) X is connected to an even vertex.
    . . . Then X becomes an odd vertex and the even vertex becomes odd.
    . . . The number of odd vertices increases by two; its parity does not change.

    (b) X is connected to an odd vertex.
    . . . Then X becomes odd and the odd vertex becomes even.
    . . . The number of odd vertices does not change.


    Continue to connect (or not connect) X to other vertices.

    If X is an even vertex, we have covered the results in (a) and (b) above.

    If X is an odd vertex, connecting it to another vertex makes X even.
    . . The vertex X is connected to will change from even-to-odd or odd-to-even.
    In both cases, the evenness or oddness of O is unchanged.


    Bottom line: adding a vertex does not change the parity of O.


    Let's begin with the simplest graph: one vertex.
    . . It is a 0-vertex, so there is one even vertex: E = 1.
    . . There are no odd vertices, so: O = 0, an even number.

    We have shown above that adding vertices does not change the parity of O.
    No matter how many vertices are added and how they are connected to existing vertices,
    . . the number of odd vertices will remain even.

    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1
    The proof of the theorem that TPH quoted is so elegant. It works for any graph.
    The sum of the degrees of the vertices of a graph equals twice the number of edges.
    This is call the ‘Handshaking Theorem’ is modern texts, but it is due to Euler.
    Proof:
    By adding the all the degrees of the vertices involves the question “How many times does each edge get counted?” Each edge involves two vertices (even loops by definitions). Thus each edge is counted twice.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: August 17th 2010, 09:23 AM
  2. Replies: 0
    Last Post: October 5th 2009, 06:54 PM
  3. Replies: 1
    Last Post: February 15th 2009, 06:35 AM
  4. how many vertices does this graph have.....
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 27th 2008, 07:30 PM
  5. Vertices of a simple graph
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 8th 2007, 04:37 PM

Search Tags


/mathhelpforum @mathhelpforum