Results 1 to 2 of 2

Math Help - Graph Theory Probe

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    UK
    Posts
    15

    Graph Theory Probe

    Could someone please assist with the following question:


    Show that every nontrivial connected graph has a closed spanning walk that contains
    every edge exactly twice.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Graph Theory Probe

    Induct on the number of verticies.
    It's true for a (the) connected graph with 2 vertices. You can check the same for 3 verticies.
    Suppose it's true for all simple connected graphs of N or fewer verticies, N>=3.
    Let G be any connected graph with N+1 verticies.
    Pick a vertex v in G.
    Suppose G - v breaks into connected graphs G1, G2, G3, .. Gm.
    If can show how to do it with those graphs individually, so that you start and end at v in <Gi Union {v}>, then you can do it for all of them, and hence for G.
    That's because you'd start at v, go through G1 returning to v, then go through G2 returning to v, etc..

    How how do you do it for one?
    Suppose {x1, x2, ... xn} are v's neighbors in G1.
    First note that v has has at least one neighbor in G1 (the original G wouldn't be connected otherwise).
    If v has more than one neighbor in G1, then begin the walk with the walk (v, x1, v, x2, v, x3, ...., v, x(n-1), v}.
    That covers all those edges exactly twice, and so just one neighbor of v in G1, xn, remains.
    Walk v to xn, but then do a cover-each-edge-exactly-twice spanning walk though G1 starting and ending at xn (induction!)
    When that walk returns to xn, then return to v.
    That covers the edge (v,xn) exactly twice, and all the edges in G1 exactly twice.
    Thus have done it for <G1 Union {v}>.
    Now, as above, repeat that process, doing v with G2, then v with G3, ... and v with Gn.
    Then have done it for all of G: a spanning walk of G, starting and ending at v, with every edge crossed exactly twice.
    That completes the induction and so proves the claim.
    Last edited by johnsomeone; September 20th 2012 at 11:47 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  2. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  3. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM
  4. Conjuncture a Formula and Probe it Using Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 11th 2010, 02:04 PM
  5. A fictitious space probe...
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: March 28th 2007, 05:36 PM

Search Tags


/mathhelpforum @mathhelpforum