Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A Every graph GG containing a cycle satisfies g(G)≤2d+1

Tags:
  1. Apr 11, 2017 #1
    Proof: Let C be a shortest cycle in G. If g(G)>= 2diam(G) + 2, then C has two vertices whose distance in C is at least diam(G)+1.
    Question: why is it at least diam(G)+1?

    cont. of proof: In G, these vertices have a lesser distance; any shortest path P between them is therefore not a subgraph of C.
    how i understood: A path "around" the cycle creates a longer path than the shortest path between x and y in G. Therefore, this shortest path P is not a subgraph of the shortest cycle C.

    rest of the proof: Thus, P contains a C-path xPy. Together with the shorter of the two x-y paths in C, this path xPy forms a shorter cycle than C, a contradiction.
    Question: why does P contain a C-path xPy if it is not a subgraph of C?
     
  2. jcsd
  3. Apr 11, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    If you have a cycle with 2n elements, then elements on opposite sides have a distance of n. Here n=diam(G)+1.
    If you limit the paths to parts of the cycle, you might make a detour, sure, and there are conditions where you certainly make a detour for some elements. That's the point that leads to the contradiction later.
    I'm a bit confused by the phrasing here, but I think the idea should get clear. We replace the longer path in C between x and y by the shorter path found above.
     
  4. Apr 11, 2017 #3
    thank you! i have diestel's free version of his book. the newer version might have better phrasing
     
  5. Apr 11, 2017 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I don't have the book, so I don't see the full proof, but the elements shown here seem to have a problem. We cannot guarantee that the shorter path P between X and Y does not contain elements of both "sides" of C. If it does, we cannot easily replace one part of C by this shorter path. That needs some more thought.
     
  6. Apr 11, 2017 #5
    another question. why would it be valid to make an assumption that "In G, these two vertices have lesser distance,"?
    I am not sure what you mean by sides of C. My follow up question is how is it valid to assume that "In G, these two vertices have lesser distance"? I think that it might not be true for all cases of graph G. Can we even draw a graph that has girth of 2diam(G) + 2?
     
  7. Apr 11, 2017 #6
    In fact, that is the entire proof in the book.
     
  8. Apr 11, 2017 #7

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The distance is at most diam(G) by definition of diam(G).
    For ever pair x,y of vertices in C, C has two paths connecting them.
    We can find such a circle in general, but it won't be the shortest circle.
     
  9. Apr 11, 2017 #8
    but since the shorter path P connecting vertices x,y won't be a subgraph of C, then it won't share elements with cycle C.. right?
     
  10. Apr 11, 2017 #9
    i can draw g(G)=<2diam(G)+1, because it's a triangle but i can't draw 2diam(G) + 2 because when the girth increases, so does the diameter of the graph - i think that's where the contradiction reveals itself
     
  11. Apr 11, 2017 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    It is not a subgraph: it has elements outside C.
    That does not mean all elements have to be outside C.

    The overall conclusion is correct, of course, but I'm not sure about the steps the proof takes.
     
  12. Apr 11, 2017 #11
    understood!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Every graph GG containing a cycle satisfies g(G)≤2d+1
  1. Can f-g ever equal g-f? (Replies: 16)

Loading...