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

[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?

 

[mfb]

Question: why is it at least diam(G)+1?

If you have a cycle with 2n elements, then elements on opposite sides have a distance of n. Here n=diam(G)+1.

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.

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.

Question: why does P contain a C-path xPy if it is not a subgraph of C?

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.

 

[Terrell]

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.

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

 

[mfb]

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.

 

[Terrell]

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.

another question. why would it be valid to make an assumption that "In G, these two vertices have lesser distance,"?

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.

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?

 

[Terrell]

I don't have the book, so I don't see the full proof

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

 

[mfb]

another question. why would it be valid to make an assumption that "In G, these two vertices have lesser distance,"?

The distance is at most diam(G) by definition of diam(G).

I am not sure what you mean by sides of C.

For ever pair x,y of vertices in C, C has two paths connecting them.

Can we even draw a graph that has girth of 2diam(G) + 2?

We can find such a circle in general, but it won't be the shortest circle.

 

[Terrell]

For ever pair x,y of vertices in C, C has two paths connecting them

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?

 

[Terrell]

We can find such a circle in general, but it won't be the shortest circle.

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

 

[mfb]

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?

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.

 

[Terrell]

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.

understood!