2
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ (2) is obviously false: $m/n$ need not even be an integer. Are you sure you've reproduced it correctly? $\endgroup$ Jul 12, 2012 at 21:53
  • 1
    $\begingroup$ I produced it word for word. Perhaps $m/n$ is a lower bound? I think perhaps the question meant that the subgraph has no vertex of degree less than $m/n$? $\endgroup$
    – EuYu
    Jul 12, 2012 at 21:54

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I have added a solution obtained from your hint. I have chosen to accept this answer since you have helped me in both parts. Thank you for your help and patience. $\endgroup$
    – EuYu
    Jul 15, 2012 at 0:41
1
$\begingroup$

For (2), what happens if you throw out all vertices which have degree less than $\frac{m}{n}$? Do you get an empty graph? If not, can you prove why this graph isn't empty? (Perhaps you should proceed by induction.)

$\endgroup$
5
  • $\begingroup$ But throwing out vertices changes the degree of the remaining graph. I am not sure how removing a vertex will alter the degree of the remaining vertices. $\endgroup$
    – EuYu
    Jul 12, 2012 at 22:50
  • 1
    $\begingroup$ @EuYu Since Code-Guru hinted at induction, you should consider just throwing out one vertex at a time. How does deleting one vertex of low degree affect the (average) degree of the remaining vertices? $\endgroup$
    – Erick Wong
    Jul 13, 2012 at 0:18
  • 2
    $\begingroup$ @ErickWong Thank you Erick and Code-Guru for your help. I have updated the question with a solution to part 2 which I obtained taking your advice. If you can give me some hints for the last part, that would be greatly appreciated! $\endgroup$
    – EuYu
    Jul 13, 2012 at 6:00
  • $\begingroup$ @EuYu I was just winging and hadn't thought through the whole solution. I've studied some graph theory recently where proofs like this came up, so it seemed like a resonable suggestion. I'm it helped you find the rest of the solution on your own. $\endgroup$
    – Code-Guru
    Jul 13, 2012 at 15:45
  • $\begingroup$ Regardless, it helped me find the solution and for that I am grateful. Thank you! $\endgroup$
    – EuYu
    Jul 15, 2012 at 0:40

You must log in to answer this question.

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