Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
(2) is obviously false: $m/n$ need not even be an integer. Are you sure you've reproduced it correctly? –  Chris Eagle Jul 12 '12 at 21:53
1  
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$? –  EuYu Jul 12 '12 at 21:54
add comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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. –  EuYu Jul 15 '12 at 0:41
add comment

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.)

share|improve this answer
    
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. –  EuYu Jul 12 '12 at 22:50
1  
@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? –  Erick Wong Jul 13 '12 at 0:18
2  
@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! –  EuYu Jul 13 '12 at 6:00
    
@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. –  Code-Guru Jul 13 '12 at 15:45
    
Regardless, it helped me find the solution and for that I am grateful. Thank you! –  EuYu Jul 15 '12 at 0:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.