2
$\begingroup$

I am looking for hints on how to solve following problems:
1. Show that in every simple graph, there is a path of length at least $\frac{2m}{n}$.
2. In $G$ there is a cycle $C$ and a path of length $k$, that connects two vertices from $C$. Show that there is a cycle of length at least $\sqrt{k}$ in $G$.
3. For all $k$, give an example of graph $G$ with longest cycle $C$ of length shorter than $4\sqrt{k}$ and which has a path of length $k$ connecting two vertices from $C$.
Can anyone help? In the first one I tried induction but it didn't work, as for the other two I have no idea how to start.

  • 0
    What are m and n? I think you need to be more precise about what is being assumed.2011-01-03

2 Answers 2