1

Suppose $G$ is a simple graph and $\delta \ge 2$. Prove G has a cycle with at least $\delta+1$ vertices

This is all I think about this problem:

Consider the longest path in the graph. for example P: $v_0$ $e_1$ $v_1$ ... $e_k$ $v_k$ then we shoud talk about neighbor vertices of the $v_k$

.

But I dont know what can I say and how to solve it!

Fareed Abi Farraj
  • 3,446
user808266
  • 123
  • 1
    You can find this question already here. For example https://math.stackexchange.com/questions/1800213/if-every-vertex-in-a-graph-g-has-degree-d-then-show-that-g-must-contain-a-cir, and https://math.stackexchange.com/questions/699867/let-g-be-a-graph-of-minimum-degree-k1-show-that-g-has-a-cycle-of-length – halrankard2 Oct 15 '20 at 18:53
  • What is $\delta$? – M. Winter Oct 15 '20 at 19:30

2 Answers2

0

Consider the longest path in G. Let this longest path $P$ be denoted by the vertices $P := v_1, v_2, \ldots, v_k$. Suppose that $v_k$ had a neighbor $w$ that was not in the set $S = \{v_1, v_2, \ldots, v_{k-1}\}$. This is a contradiction because then the path $v_1, v_2, \ldots, v_k, w$ would be longer than $P$. This tells us that $v_k$ only has neighbors in $S$. Now start walking along the path $P$ from $v_1$ to $v_k$, and stop at the first vertex $v_i$ for which there is an edge $(v_i, v_k)$ in the graph G. We know such a vertex must exist since $\delta$ is at least two and $v_k$ has all its incident edges in the set $S$. Consider the cycle $C := v_i, v_{i + 1}, \ldots, v_k, v_i$. Since $v_k$ didn't have any edges to the vertices $v_1, v_2, \ldots, v_{i-1}$ this means that $v_k$ must only have neighbors in the smaller set $S' = \{v_i, v_{i + 1}, \ldots, v_{k-1}\}$. If $\delta$ were bigger than the number of vertices in this set $S'$, there would be no way that $v_k$ could have at least $\delta$ edges incident, which is required. In other words, $\delta \leq |S'| = k - i$. Note that the cycle $C$ has exactly $k - i + 1$ edges, so $\delta + 1 \leq k - i + 1 = length(C)$.

user825920
  • 73
  • 4
0

Let $P = v_1,\ldots, v_k$ be a longest path in $G$ and suppose $\delta(G)\ge 2=\delta$. Then there are at least $\delta-1$ edges from $v_k$ incident with vertices $W=\{v_1,\ldots, v_{k-2}\}$.

Let $U=\{v_1,\ldots,v_{k-\delta}\}$ and $V=\{v_{k-\delta+1},\ldots, v_{k-2}\}$ and observe that $U\cup V=W$ and $|V|=\delta-2$. So there must be at least 1 edge from $v_k$ that connects to $U$, say $v_i$. Then $C$, the cycle starting at $v_i$ along $P$, will include at least the vertices $v_i$, all the vertices of $V$, $v_{k-1}$ and $v_k$. That is to say $C$ will have at least $\delta+1$ vertices.

Laars Helenius
  • 7,965
  • 1
  • 23
  • 35