5
$\begingroup$

Let $G$ be a graph such that $\delta(G) \geq k$.

  1. Prove that $G$ has a path of length at least $k$.

    Solution: We know that $\delta(G) = \min\lbrace \deg(v) \mid v \in V(G) \rbrace$

    If $\delta(G) = k$ then there exists some $v \in V(G)$ such that $\deg(v) = k$. This means all other vertices $u \in V(G)$ have $\deg(u) \geq k$.

    Now I know this must be part of the proof. How would I prove that there exists a path of at least $k$?

  2. If $k \geq 2$, prove that $G$ has a cycle of length at least $k+1$.

  • 3
    The title should be a precise 1-line summary of what your question is about, not the 1st sentence of the question.2010-08-11
  • 0
    edited title due to comment2010-08-11

3 Answers 3

3

b) consider a path $v_0\dots v_k$ of length $k$ (existing for part a) and for Chandru's construction) such that $v_i \neq v_j$ $\forall i\neq j$.

  • If $v_0$ and $v_k$ are adjacent, you have a cycle of lenght $k+1$.
  • Otherwise, since $deg(v_k)\geq k$, $v_k$ has at least one adjacent vertex $v_l$ with $l>k$ and you can extend the path with this new vertex. If $v_l$ is adjacent with $v_0$ or $v_1$ you're done, otherwise you can extend the path again with a vertex that doesn't belong to the path yet. Since $G$ has only a finite number of vertices, at some point you will find a vertex $v_n$ whose adjacent vertices are all part of the path. $deg(v_n)\geq k$, so $v_n$ is adjacent to $v_i$ for some $i< n-k$ and you can finally close the path with a cycle of lenght $n-i \geq k+1$.
2

You can construct path and cycle inductively. Start at an arbitrary vertex $v_0$, and move along an arbitrary edge to $v_1$. Since vertex $v_1$ has degree k or greater, it has at least $k-1$ neighbours other than $v_0$. Move along an edge to one of these neighbours $v_2$. Since vertex $v_2$ has degree $k$ or greater, it has at least $k-2$ neighbours other than $v_0$ and $v_1$. Move along an edge to one of these neighbours $v_3$. And so on... until you reach vertex $v_k$. At this stage, you already have a path of length $k$. There may then be no unvisited vertices left to move to, in which case v_0 must be one of them, and you can return to it for a cycle of length k+1. Otherwise, just keep on moving to new vertices. If when you get to vertex v_n you find that it is connected to one of the vertices $v_j$ for $0 \leq j \leq (n-k)$ then you can go back to that vertex for a cycle of length k+1 or greater. If not, then v_n will have a neighbour that you have not yet visited, and the journey can continue. Assuming that G has only finitely many vertices, you must eventually complete a cycle.

  • 0
    "There may then be no unvisited vertices left to move to, in which case v_0 must be one of them, and you can return to it for a cycle of length k+1." - how do you know that vk is adjacent to v0?2010-08-11
2

a) Take a maximal path $P=v_0v_1 \ldots v_l$. As $P$ is maximal, all neighbourghs of $v_0$ are in $P$. As $v_0$ has at least $k$ neighbourghs, then $l \geq k$.