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.
Approximations of cycle/path lengths in graphs
2
$\begingroup$
graph-theory
-
0What are m and n? I think you need to be more precise about what is being assumed. – 2011-01-03