2
$\begingroup$

An answer is $\lfloor(2n+2)/3\rfloor$ and I was asked to prove it.

I am new to graph theory and I really have no idea how to relate girth with the number of edges in a graph.

The next problem is to prove that for a graph with $n$ vertices and $n+2$ edges, the girth is at most $\lfloor(n+2)/2\rfloor$. I guess they can be solved in similar ways. I see it's two thirds the number of edges in the first problem and a half that in the second but I can not figure out where these coefficients come to play.

$\endgroup$

1 Answer 1

2
$\begingroup$

Here is a SKETCH. You can fill in the details.

That this is a lower bound: Let $u$ and $v$ be vertices, and let $P_1,P_2$, and $P_3$ each be internally vertex-disjoint paths with endpoints $u$ and $v$, and each with either $\lfloor \frac{2n-2}{3} \rfloor$ or $\lceil \frac{2n-2}{3} \rceil$ internal vertices, so that the total number of vertices is $n$. What is the number of edges in the resulting graph, and then what is the length of the smallest cycle in the resulting graph? Assuming that $P_1$ and $P_2$ are the two shortest paths of $P_1,P_2, P_3$, note that the length of the smallest cycle is the number of vertices in $P_1$ plus the number of vertices in $P_2$, plus 2. How much is this?

This is an upper bound: $G$ be such a graph and let us assume that $G$ is connected [why can you assume that?]. Let us also asume that $G$ has no vertices of degree-1 [why can you assume that?] Now let $C$ be a cycle in $G$. Let us assume that $C$ has more than $\lfloor \frac{2n+2}{3} \rfloor$ vertices lest we would be already done.

Now as $G$ has $n+1$ edges there is a vertex $v \in C$ incident to an edge $e$ not in $C$. Now take a nonbacktracking walk $W$ from $v$ via this edge $e$, and stop either when this walk $W$ either (a) repeats a vertex, or (b) lands on another vertex $u$ in $C$. [Note that as every vertex has degree 2, note that $W$ must either terminate when it repeats a vertex or runs back into $C$; i.e., $W$ cannot terminate on a degree-1 vertex. Then $W$ has length no more than $n$ minus the number of vertices in $C$.

If (a) happens then, as every vertex in $G$ has degree at least 2, the length of the shortest cycle in $G$, is no more than the length of $W$, which is $n$ minus the number of vertices in $C$. Which, as $C$ has more than $\lfloor \frac{2n+2}{3} \rfloor$ vertices, is clearly no more than $n/2 < \lfloor \frac{2n+2}{3} \rfloor$. What about if (b) happens? [ONE MORE HINT: If (b) happens then $G$ has 3 internally-vertex-disjoint paths $P_1,P_2,P_3$ each with endpoints $u$ and $v$. What is an upper bound on the sum of the shortest two such paths?]

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .