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

Tags:
1. Apr 11, 2017

### Terrell

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. Apr 11, 2017

### 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.

3. Apr 11, 2017

### Terrell

thank you! i have diestel's free version of his book. the newer version might have better phrasing

4. Apr 11, 2017

### 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.

5. Apr 11, 2017

### Terrell

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?

6. Apr 11, 2017

### Terrell

In fact, that is the entire proof in the book.

7. Apr 11, 2017

### 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.

8. Apr 11, 2017

### Terrell

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?

9. Apr 11, 2017

### Terrell

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

10. Apr 11, 2017

### 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.

11. Apr 11, 2017

understood!