Results 1 to 7 of 7

Math Help - Interesting Graph Theory Proof

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    23

    Interesting Graph Theory Proof

    Hey guys,

    I don't want the answer to this I just want some help being able to explain this. I have just started doing graph theory in class, and haven't really figured out how to do the proofs yet. This problem just makes complete sense to me so its one of those that is hard to explain in a "proofy" way for me. Thanks for anyone's help in advance. The question is:

    Let G=(V,E) be a graph in which every vertex has degree at least k\ge 1. Show that there is a path of length at least k in G.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by SaxyTimmy View Post
    Let G=(V,E) be a graph in which every vertex has degree at least k\ge 1. Show that there is a path of length at least k in G.
    Assume that the graph is a simple graph. A path is an alternating sequence of vertices and edges in which on vertex is repeated. (Now in Graph Theory definitions will vary, but this argument should work.)

    We can assume that each vertex is of degree K where K \ge 1.
    The key concept is that there must be at least K+1 vertices in the graph.
    Start at any vertex. There are K vertices adjacent to that vertex.
    Choose a second vertex adjacent to the first. Now there are K-1 vertices, other than the first, adjacent to the second vertex.

    Do you see how finish?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2008
    Posts
    23
    No.... I guess I don't see how to finish. This sucks I thought I completely understood graph theory last week and now this LOL.... oh well if you have extra tips it would be great if not. I will just put a bunch more thought into it.

    Edit: Also, I am not sure why there would have to be K + 1 edges for this. Isn't it possible to have more than one edge connecting two vertices? or is this a rule of graphs? I am really not sure we haven't discussed this in class.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    bbq
    bbq is offline
    Newbie
    Joined
    May 2008
    Posts
    2
    You may keep on moving to adjacent vertices until there are 0 vertices adjacent to the current vertex untravelled. This gives you a path of length k? Adding more edges will not reduce the length of the path, so there is a path of length at least k?
    Last edited by bbq; July 20th 2008 at 07:37 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by SaxyTimmy View Post
    Also, I am not sure why there would have to be K + 1 edges for this. Isn't it possible to have more than one edge connecting two vertices? or is this a rule of graphs? I am really not sure we haven't discussed this in class.
    Did not say that there are K+1 edges, in fact there are more edges.
    This is true: there must be at least K+1 vertices in the graph.
    To finish. Choose a third vertex adjacent to the second but not the first, there at least K-2 to choose.
    By this inductive process we can sequence of K+1 vertices in a path.
    That means the path is length K.

    Now, I did say that this was for a simple graph, no multiple edges.
    Depending upon the definition of path, using the one I gave above there is a simple counter-example using a two-vertex multi-graph.

    How does your text define a path?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2008
    Posts
    23
    Hey,

    Sorry I had meant vertices not edges.
    For us a path has been defined as: A sequence of distinct vertices v0, v1, v2, ..., vk where each pair of successive vertices {vi, vi+1} form an edge, where i=0...k-1.

    Sorry, that I cant use latex for it, but I think that it should be self explanatory (numbers to the right of letters are generally subscripts).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    If a vertex is of degree 2 then there must two distinct vertices (in a simple graph) adjacent to it. That makes 3 vertices. If each vertex has degree at least K then there must be at least K+1 vertices.

    Again, there is a counter example to this statement if you use multi-graphs.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 20th 2010, 02:27 AM
  2. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2010, 11:59 AM
  3. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 5th 2010, 08:34 AM
  4. Graph theory: proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 29th 2009, 12:00 PM
  5. Graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 26th 2009, 09:01 PM

Search Tags


/mathhelpforum @mathhelpforum