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

share|improve this question
    
What are m and n? I think you need to be more precise about what is being assumed. –  Joseph Malkevitch Jan 3 '11 at 18:48
add comment

2 Answers 2

Proof for the first question : Suppose not. If there exists a graph G such that there is no path of length at least its average degree d = 2m/n. Pick a graph G of all such graphs with minimum number of vertices. Now, let the minimum degree of G be x. If x<=d, then delete the vertex from G and all its incident edges and get G'. Let the avg degree of G' be d' and G' has less vertices than G and d' >= d. So, G' is not a counter example for the above statement. So, there is a path of at least average degree d'. But the path in G' is also a path in G. So, there is a path of length d' in G as well. But d'>=d, so, there exists a path of length at least d in G.

share|improve this answer
add comment

Here are some hints.

  1. try to use induction, but instead of taking out one edge (or one vertex), take out a spanning tree (when you can), and if the graph is not connected, show that it has a "big enough" sub graph so that $\frac {|E'|}{|V'|} \geq \frac {|E|}{|V|}$

  2. write $P=(v_1, ..., v_k)$ and $C=(u_1,...,u_t)$ such that $v_1=u_1$ and $v_k=u_i$ for some i. The problem arises when there are a lot of intersections between P and C. Suppose $i\leq t/2$ , so if $u_2=v_j\in P$ (or generally, the first vertex in C after $u_1$ that is in P), then if $j\geq \sqrt{k}$ we have the cycle $(v_1,...,v_j)$. Other wise , j is small, and we look for the second intersection. So we see that two intersections must be near enough on the one hand, but they must be far enough on the other hand, because the first one is with $v_1$ and the last one is with $v_k$.

  3. Here I think you should use a graph that have a cycle of length $4\sqrt{k} $ and then "square" it, so it has 4 sides of size $\sqrt{k}$ (I think of the vertices as $(i,j),\; 1\leq i,j \leq \sqrt{k})$. Now construct a path the start with (1,1) goes to (2,2) and then right until $(2,\sqrt{k})$. then it goes down again to $(3,\sqrt{k}-1)$ and left until (3,1) etc.

I hope this helps.

share|improve this answer
add comment

Your Answer

 
discard

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