The number of edges when girth is large

Question

For any positive constant $c$, the girth of graph $G$ is at least $cn$, where $n$ is the number of vertices. Show that, the number of edges, $\vert E \vert \leq n + o(n) $. Now I know that we should consider the function $f(n) = max \{e(G) \} -n$, where the graph $G$ is as above. A claim states that $\frac{f(n)}{n}$ is decreasing.

Answer 1

**

Not a full answer

**

Proposition:

Let $G=(V,E)$ be a graph with $n$ vertices. For $k=O(1)$ with respect to $n$ $$\text{girth}(G)\geq\frac{n}{k}\implies \vert E\vert\leq(n-1)+k$$

Conclusion:

$$\text{girth}(G)\in\Omega(n)\implies E(G)\leq n+\color{red}{O}(1)\implies\text{girth}(G)\in\Omega(n)\implies E(G)\leq n+\color{red}{o}(n)$$

Proving the proposition seems, at first sight, simple.
For example by using the fact that if $G$ contain a cycle, then $g(G)\leq 2\cdot\text{Diam}(G) + 1$, which was proved here

I'll try to write a complete proof it this hint does not help you, or was trivial.

Answer 2

$\mathbf{Intuition:}$ The question intuitively is asking us that if the graph is super sparse, then does it behave more or less like a tree? One more way of looking at the problem is that the average degree must go more towards 2 and that the number of vertices of large degree must vanish. We just have to make this rigorous.

$\mathbf{Proof:}$ Start with some $\epsilon > 0$ such that girth $\geq \epsilon n$ . Suppose for the sake of contradiction, if $\frac{e(G)-n}{n}$ doesn't go to zero, there is a $\delta>0$ such that $e(G)>(1+\delta)n$ for a sequence of $n$ going to infinity. Clearly, for a graph with maximal edges, it can't have zero degree vertices. Now, excise all vertices of degree one, we lost the same amount of edges and vertices. Keep doing this till all vertices are of degree 2 or higher. We can see that in the new graph $G'$, $e(G')>(1+\delta)V(G')$.

Now, perform the following operation on the graph $G'$. If there is a path or a cycle of length greater than $\frac{1+\delta}{\delta}$ such that the endpoints of the path (if it's a cycle, delete the whole thing) are of degree more than 2, delete all the vertices except the end points. For a path or cycle, we lose $g$ edges and $g-1$ vertices. A calculation gives that the new graph after performing this also satisfies $e(G'')>(1+\delta)V(G'')$. Also, make the following observation, by removing these vertices and edges, we do not actually lose girth in the graph. In fact, it can only become higher. If we actually end up with an acyclic graph after these deletions, then the result is at most a tree and we can then get the no. of edges and vertices for the tree easily and see the $\frac{e(G)-n}{n}$ does go to zero.

Now, contract the vertices of degree 2 in this graph $G''$ to arrive at a graph $G'''$ of minimal degree 3 (possibly with loops). Each edge corresponds to a path or cycle in $G''$ of length at most $\frac{1+\delta}{\delta}$. The graph $G'''$ of minimal degree 3 must contain a cycle of length lesser than $2log_2(V(G'''))$. The vertices in $G'''$ is at most the no. of vertices in $G''$ as we don't introduce new vertices.

From this, we have that there is a cycle in $G''$ of length at most

$2(\frac{1+\delta}{\delta})log_2(V(G'')) \leq 2(\frac{1+\delta}{\delta})log_2(n)$. But the girth of $G''$ is at least the girth of $G$ which is $\epsilon n$. And this can't hold for large enough $n$, which gives us a contradiction.