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

Tags:
1. Apr 11, 2017

Terrell

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
N/A

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

nuuskur

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?

3. Apr 12, 2017

Terrell

sorry for that, my book did not define diameter correctly which lead to my confusion.