# An upper bound of the girth of a simple graph with $n$ vertices and $n+1$ edges

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.

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