Graph $G$ has $n$ vertices and $mn$ edges, where $n>2m$, show that there exists a path with $m+1$ vertices. (A path is an open walk without repeating vertices )
Problem
Source: singapore MO senior section round 2 P2
Tags: graph theory, singapore, combinatorics
03.07.2019 11:08
bump....
04.07.2019 04:23
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.
04.07.2019 04:35
, one can prove that there exists a cycle of length at least $2m+1$, hence there exists a path with $2m+1$ vertices.
04.07.2019 05:26
This seems to be a very useful lemma. Is there a name for it? Could you provide proof?
04.07.2019 06:23
MNJ2357 wrote:
, 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$??
04.07.2019 14:04
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.
04.07.2019 14:08
Mathlover_SH wrote: MNJ2357 wrote:
, 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.
04.07.2019 16:20
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$.
04.07.2019 16:26
Taha1381 wrote: Mathlover_SH wrote: MNJ2357 wrote:
, 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!
05.07.2019 17:09
Mathlover_SH wrote: MNJ2357 wrote:
, 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.
07.07.2020 18:45
Is this a strong result? https://artofproblemsolving.com/community/c6h1946411p14944311
28.08.2023 00:54
Taha1381 wrote: Mathlover_SH wrote: MNJ2357 wrote:
, 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
28.08.2023 00:56
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
13.08.2024 23:24
MNJ2357 wrote:
, 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.