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.
 A: 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?]
