Given a graph with n vertices, if it have more than $\frac{nt}{2}$ edges then there exists a simple path of length $t+1$.

Question

I have been working on this problem for a while, and yet I do not have a clear lead. Currently all I have is that the average degree is greater than $t$ so exists a vertex with degree at least $t+1$, however it does not seem to work. I have also tried shrinking $c_n$ into a single vertex, or induction on $n$ and $t$, but have no clue how to refine the ideas into a real working proof.

There is a similar question here, where it is proved that a path of length at least $t$ exists. This result is one off my bound however, and I have no way to improve it.

Thanks.

Answer 1

It's not true.

Suppose $n > 2$.

Let $t=1$, and consider a graph of order $n$ with one vertex $v$ of degree $n-1$, and no edges other than those incident with $v$.

Since $n > 2$, we have $$n-1 > \frac{n}{2} = \frac{nt}{2}$$ but there is no path of length $t+2=3$.

Update:

In the edited version of your question, the new goal is to prove that there is a path of length $t+1$.

Let $m$ be the number of edges.

By the referenced link

$\qquad$$G$- simple graph. Show that it has a path of length at least $\dfrac{2m}{n}$ where $m=|E|$ and $n=|V|$

there must be a path of length $L \ge {\large{\frac{2m}{n}}}$.

But then, since $m > {\large{\frac{nt}{2}}}$, we get $$L \ge \frac{2m}{n} > \frac{2\left(\frac{nt}{2}\right)}{n} = t$$ Then, since $L$ is an integer, and $L > t$, we get $L \ge t+1$, as required.

Answer 2

It's false. Let $t=(n-1).$ Then your graph is the complete graph on $n$ vertices, so the longest simple path has length $n-1$ ($n$ if you allow cycles), so there is no simple path of length $t+2 = n+1.$