2
$\begingroup$

I have the problem: Let $d>1$ be an integer. Prove that if every vertex of a graph $G$ has degree at least d, then G contains a cycle of length at least $d + 1$.

I'm pretty sure this can be done by induction and the base case would be a connected graph of 3 vertices for which every vertex has degree 2 and G has a cycle of length 3. I don't really know where to go from here though.

I think it may have something to do with the fact that the graph with minimum degree $d+1$ would need $d+1$ edges added to the graph which satisfies the proposition for $d$, but I don't know how to take that further.

$\endgroup$
1
$\begingroup$

Take a maximal path $u_0\dots u_n$. Now, since the path is maximal $u_0$ has all of its neighbours inside the path, there are at least $r$ of these by hypothesis.

So at least $r$ elements of $u_1,u_2\dots u_n$ are neighbours of $u_0$, the last of these elements must be of the form $u_j$ with $j$ at least $n$.

The cycle $u_0,u_1,u_2,\dots u_j,u_0$ is the desired one.

$\endgroup$
1
$\begingroup$

Let $\delta(G)$ denote the smallest degree in a graph $G$. For a graph $G$, if $\delta(G)=d$, then $G$ contains a path of length $d$ and, furthermore, if $d>1$, then $G$ contains a cycle of length $d+1$.

Proof. Let $d\geq 1$ and suppose that $G$ is a graph with $\delta(G)=k$. Let $P$ be a longest path in $G$, between, say, $u$ and $v$. Since $P$ is maximal, every neighbor of $u$ is in $P$; since $u$ has at least $d$ neighbors, $P$ has at least $d$ vertices besides $u$, that is, $P$ has length at least $d$. If $d\geq 2$, the edge to the farthest neighbor of $u$ in $P$ completes a cycle of length at least $d+1$. $\blacksquare$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.