I was doing some practice problems in graph theory and would appreciate some help on this one. This problem is from a practice exam from the discrete mathematics course at Princeton.
Consider a graph $G$ on $n$ vertices that has no cycles of length $\le 2k+1$. Let $m$ be the number of edges in the graph. The goal of the problem is to prove that $m \le n^{1 + \frac{1}{k}} + n$.
1) What is the average degree in $G$?
Since there are $m$ edges, the total degree is $2m$. The average degree is therefore $\frac{2m}{n}$.
2) Prove that there exists a subgraph $H$ of $G$ with minimum degree $\frac{m}{n}$. The hint given is: Think about vertices which have degree less than $\frac{m}{n}$.
I have no idea how to proceed with this one. I am pretty sure that this part of the problem does not require the minimum cycle condition. I think that some kind of bounds is required.
3) Let $v$ be a vertex in $H$. Consider the subgraph of $H$ induced by vertices at distance at most $k$ from $v$. Prove that this subgraph is a tree.
If the subgraph were not a tree, there would exist a cycle. However, all vertices are distance at most $k$ and so the cycle would be of length at most $2k +1$, contradicting the initial hypothesis.
4) Prove that $\frac{m}{n} \le n^{\frac{1}{k}}$ + 1. (Hint: Give bounds on the number of vertices in the subgraph constructed in part 3.)
Again, I'm not too sure how to find an appropriate bound.
I would greatly appreciate some guidance for this problem, especially for part 2 with the existence of the subgraph. Thank you for your time.
Edit: Solution to part 2 obtained thanks for Code-Guru and Erick Wong's help.
We induct on the number of vertices. Let $\nu$ be the average degree of the graph. Given a one vertex graph, we have average degree $\nu=0$. There exists trivially a subgraph with minimum degree $\frac{\nu}{2}$, i.e. the single vertex graph itself. This forms our base case.
Suppose then that every graph on $n-1$ vertices has a subgraph with minimum degree $\frac{\nu}{2}$. Consider a graph $G$ on $n$ vertices. If the graph contains no vertices $v$ with $\deg{v} < \frac{\nu}{2}$ then we are done.
Otherwise, fix such a $v$ and remove it. Since $\deg{v} < \frac{\nu}{2}$ we remove at most $\nu$ degrees from the total degree of the graph. The average degree of the $n-1$ vertex graph is then
$$\nu_{n-1} \ge \frac{n\nu – \nu}{n-1} = \nu$$
More specifically, the average degree is non-decreasing. Therefore by the inductive hypothesis, there exists a subgraph of $G\backslash\{v\}$ with minimum degree at least $\frac{\nu_{n-1}}{2} \ge \frac{\nu}{2}$ which is also the desired subgraph of $G$ itself.
The result holds by mathematical induction. $\square$
Edit 2: Solution to part 4 thanks to Erick Wong
We consider the tree obtained in part 3 as a rooted at $v$. $v$ has at least $\frac{m}{n}$ children because of it's degree bound. Similarly, each subsequent child has at least $\frac{m}{n} – 1$ children. Therefore we obtain a lower bound for the number of vertices as
$$v_T \ge 1 + \frac{m}{n} + \frac{m}{n}\left(\frac{m}{n}-1\right) + \cdots + \frac{m}{n}\left(\frac{m}{n} – 1\right)^{k-1}$$
We evaluate the sum as a geometric series
$$v_T \ge 1 + \frac{m}{n}\left(\frac{\left(\frac{m}{n}-1\right)^k – 1}{\frac{m}{n}-2}\right)$$
If $\frac{m}{n} \le 2$ then the required bound is trivial. So consider $\frac{m}{n} > 2$. Our inequality becomes
$$n \ge v_T \ge 1 + \frac{m}{n}\left(\frac{\left(\frac{m}{n}-1\right)^k – 1}{\frac{m}{n}-2}\right)$$
$$m – 2n \ge \frac{m}{n}\left(\frac{m}{n}-1\right)^k – 2$$
$$n – 2n\cdot\frac{n – 1}{m} \ge \left(\frac{m}{n}-1\right)^k$$
$$n \ge \left(\frac{m}{n}-1\right)^k$$
$$n^{\frac{1}{k}} + 1 \ge \frac{m}{n}$$
as required. $\square$
Best Answer
For part (4), there is a fairly innocent typo in the question: it should read $$\frac{m}{n} \le n^{1/k} + 1.$$
After part (3), you have found a tree $T$ within the subgraph $H$. Picture this as a rooted tree starting from $v$, and it is easy to see how many children $v$ has. How many children does each child of $v$ have? You can get a slightly different lower bound here too. How many levels does $T$ have?
Can you use these to give a lower bound for the number of vertices of $T$?