1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How to construct a graph with girth = twice the diameter + 1

  1. Apr 11, 2017 #1
    1. The problem statement, all variables and given/known data
    I am trying to verify this theorem for myself.
    Theorem: Every graph G containing a cycle satisfies g(G)≤2diam(G)+1

    2. Relevant equations

    3. The attempt at a solution
    i have drawn graphs and i failed to verify the theorem. is it even possible, since increasing the girth directly increases the diameter of the graph...?

    However the theorem has a proof.

    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. In G, these vertices have a lesser distance; any shortest path P between them is therefore not a subgraph of C. 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.
  2. jcsd
  3. Apr 12, 2017 #2
    This seems kind of obvious.

    Let the maximum eccentricity (diameter) be ## D## and the length of the shortest cycle be ## L##. Assume, for a contradiction, a finite graph ## G## is picked such that ##L>2D+1 ##. Then the graph ## G## contains two vertices with a distance of at least ##2D+1 ##, an immediate contradiction. Do you understand what the contradiction is?
  4. Apr 12, 2017 #3
    sorry for that, my book did not define diameter correctly which lead to my confusion.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted