bump....

My solution: when $n=2m+1$, complete graph, trivial when $n=3$, trivial now, assume for any graph with $n=k-1 (k>4)$ vertices and $mn$ edges, where $m \in N, 2m+1 \le n$, we can find a path with $m+1$ vertices, we show this is also true for any graph with $n=k$ vertices. Case 1: there exists a vertex $A$ such that $deg(A) \le m$ we consider graph $H=G/ \{ A \}$ (the subgraph of $G$ that has all the vertices and edges in $G$ except $A$ and the edges connecting $A$) $ |E(H)| = |E(G)| - deg (A) \ge |E(G)| - m = m(n-1)$ by induction assumption, we are done. Case 2: for any vertex $A$ in $G$, $deg(A) \ge m+1$ then we can randomly pick a vertex $A_0$, then $A_1$, a vertex connected to $A_0$, $A_1 $ doesn't belong to $ \{A_0\}$ then $A_2$, a vertex connected to $A_1$, $A_2 $ doesn't belong to $\{A_0, A_1\}$ ... and finally $A_m$, a vertex connected to $A_m$ doesn't belong to$\{A_0, A_1, ...., A_m-1\}$ because for any vertex $A$ in $G$, $deg(A) \ge m+1$, this process is doable, and $A_0 A_1 A_2... A_m$ is the path with $m+1$ vertices By mathematics induction, we are done.

Using this lemma

, one can prove that there exists a cycle of length at least $2m+1$, hence there exists a path with $2m+1$ vertices.

This seems to be a very useful lemma. Is there a name for it? Could you provide proof?

MNJ2357 wrote:

Using this lemma

, one can prove that there exists a cycle of length at least $2m+1$, hence there exists a path with $2m+1$ vertices. Are you sure?Try $k=1$ and $k=2$??

The average degree in such a graph is $2m$. Now I will state some well known lemmas. Lemma$1$:Any graph with average degree $d$ contains a subgraph with all degrees not less than $\frac{d}{2}$ Proof of lemma1:Keep deleting bad vertices untill we don't have any since the average degree increases every time we won't reach to the null graph so we will be done. Lemma2:Any graph with all vertices more than $d$ has a path of at least $d+1$ vertices. Proof of Lemma 2:Take a maximal path since the neighbors of endpoint of this path is inside the path the path has at least $d+1$ vertices. Returning back to the problem we will find a subgraph that every vertex has degree at least $m$ and then a path consisting of at least $m+1$ vertices.

Mathlover_SH wrote: MNJ2357 wrote:

Using this lemma

, one can prove that there exists a cycle of length at least $2m+1$, hence there exists a path with $2m+1$ vertices. Are you sure?Try $k=1$ and $k=2$?? You will need $k>1$ in order to apply the lemma.This is a classical result of erdos but I don't think we can use it here since it is like an atomic bomb.

Let $d_i$ be the number of nodes in the longest path ending at vertex $i$ for $1 \leq i \leq n$. Initially, $d_i = 1$ for all $i$. Consider iteratively adding the mn edges to the graph in any order and updating $d_i$. When adding an edge $(x, y)$, $d_x = d_x + 1$ if $d_x \leq d_y$ $d_y = d_y + 1$ if $d_y \leq d_x$ Since at least one of these must be true, $\sum\limits_{i=1}^n d_i \geq n + mn$ If $d_{max} < m+1$, $\sum\limits_{i=1}^n d_i \leq mn$, a contradiction. Therefore there must be a path of length $m+1$.

Taha1381 wrote: Mathlover_SH wrote: MNJ2357 wrote:

Using this lemma

, one can prove that there exists a cycle of length at least $2m+1$, hence there exists a path with $2m+1$ vertices. Are you sure?Try $k=1$ and $k=2$?? You will need $k>1$ in order to apply the lemma.This is a classical result of erdos but I don't think we can use it here since it is like an atomic bomb. Well, at least it has an elementary proof. Also, this could be a useful lemma!

Click to reveal hidden text

Mathlover_SH wrote: MNJ2357 wrote:

Using this lemma

, one can prove that there exists a cycle of length at least $2m+1$, hence there exists a path with $2m+1$ vertices. Are you sure?Try $k=1$ and $k=2$?? I think it's a typo and he meant $> \frac{n(k-1)}{2}$ instead $(k > 1)$. To see that we cannot do better, consider $n=k$ and having a $k$-clique. The proof of the result can also go the same way as said in post #7.

Is this a strong result? https://artofproblemsolving.com/community/c6h1946411p14944311

Taha1381 wrote: Mathlover_SH wrote: MNJ2357 wrote:

Using this lemma

, one can prove that there exists a cycle of length at least $2m+1$, hence there exists a path with $2m+1$ vertices. Are you sure?Try $k=1$ and $k=2$?? You will need $k>1$ in order to apply the lemma.This is a classical result of erdos but I don't think we can use it here since it is like an atomic bomb. Sometimes in the SMO we need to memorise some weird theorem that no one knows about, for example this yr's Open Round 2 #5 requires a theorem about any triangle can be divided into 7 trapeziums

SpecialBeing2017 wrote: My solution: when $n=2m+1$, complete graph, trivial when $n=3$, trivial now, assume for any graph with $n=k-1 (k>4)$ vertices and $mn$ edges, where $m \in N, 2m+1 \le n$, we can find a path with $m+1$ vertices, we show this is also true for any graph with $n=k$ vertices. Case 1: there exists a vertex $A$ such that $deg(A) \le m$ we consider graph $H=G/ \{ A \}$ (the subgraph of $G$ that has all the vertices and edges in $G$ except $A$ and the edges connecting $A$) $ |E(H)| = |E(G)| - deg (A) \ge |E(G)| - m = m(n-1)$ by induction assumption, we are done. Case 2: for any vertex $A$ in $G$, $deg(A) \ge m+1$ then we can randomly pick a vertex $A_0$, then $A_1$, a vertex connected to $A_0$, $A_1 $ doesn't belong to $ \{A_0\}$ then $A_2$, a vertex connected to $A_1$, $A_2 $ doesn't belong to $\{A_0, A_1\}$ ... and finally $A_m$, a vertex connected to $A_m$ doesn't belong to$\{A_0, A_1, ...., A_m-1\}$ because for any vertex $A$ in $G$, $deg(A) \ge m+1$, this process is doable, and $A_0 A_1 A_2... A_m$ is the path with $m+1$ vertices By mathematics induction, we are done. Also I think your part 1 of induction (the case where a vertex has less than m edges) does not work

MNJ2357 wrote:

Using this lemma

, one can prove that there exists a cycle of length at least $2m+1$, hence there exists a path with $2m+1$ vertices. This lemma is result by Erdős and Gallai. See <Combinatorial Problems and exercises>, page $439, 440$ for the proof. Actually, this is just a direct result of the following lemma, known as Generalized Dirac's theorem; Quote: If graph $G$ is $2$-connected and has minimum degree $d$, it has cycle of size at least $2d$ or hamiltonian cycle. This is result of Dirac, and proof is in same book, page $439$. It's proof is very similar to commonly known proof of Dirac theorem. Something similar one for path rather than cycle is known. According to this question, the following statement is true. Richie wrote: Let G be a simple graph on $n$ vertices having more than $\frac{n(k-1)}{2}$ edges. Prove that G has a path of length $k$. Proof is more easier here. We just need induction and following famous lemma of graph theory, the one which appeared in Diestel's <Graph Theory>, chapter $1$ problem $9$. This lemma solves it directly. Quote: Let G be a connected graph with minimum degree $d$. Then it has path length at least $2d$ or hamiltonian path. For the proof, see here.