# Prove that if every node in a simple graph $G$ has degree $3$ or higher, then $G$ contains a cycle with a chord.

By simple graph I mean a graph with no loops or double edges.

If $C$ is a cycle and $e$ is an edge connecting two non adjacent nodes of $C$, then $e$ is called a chord.

I realize that one plan of attack is to choose any node, say $v_0$. Then, since the degree of $v_0$ is $3$ there are $3$ other nodes connected to it. Repeating this argument we will eventually have to reach a node that is connected by an edge to one of the previously used nodes.

I just don't see how this guarantees the existence of a chord.

• But if a graph contains a cycle that has a chord, then the graph contains two smaller cycles, right? Do I confuse anything here? Jul 29 '13 at 15:48
• Having degree $\geq 3$ makes at least $\frac{3n}{2}$ edges, and this is essentially the same as this question. Jul 29 '13 at 16:00

Hint 1: by induction on $n$ the number of nodes. The case $n=4$ is easy. What about the induction step?

Look that only if you didn't get any ideas:

Hint 2:

If you "fusion" two nodes of such a graph, what happen?

Solution (only in case of great emergency ...)

Let $P(n)$ denotes: every node, in a simple graph $G$ with $n$ nodes, has degree 3 or higher, implies that $G$ contains a cycle with a chord.

$P(4)$ is trivially true.
The only simple graph with degree a least 3 is the fully connected graph.

Suppose $P(n)$ true.
Let $G$ be a simple graph of degree at least $3$ with $n+1$ nodes.

We call fusion of two nodes $n_1$ and $n_2$ the removal of $n_1$ and $n_2$ and the addition of a new node $f$ such that every ingoing/outgoing edges of $n_1$ and $n_2$ are now ingoing/outgoing edges of the new fusion $f$ and then removing "double edges" and self loops.

Fusion two neighbours nodes such that they have (at least) one neighbour not in comon to obtain $G'$ a simple graph of degree at least $3$ with $n$ nodes. If such nodes doesn't exists that mean your graph is fully connected (or is maid of several parts fully connected) and the property is trivial.
Otherwise, by $P(n)$ you know that it contains a cycle with a chord.
Two case:
- either the cycle does not contain $f$ then this cycle appear in $G$ hence $P(n+1)$ holds.
- Or the cycle contain $f$, unfold this cycle in the cycle containing $n_1$ and $n_2$ and you have a cycle in $G$ and the cord is still present (either connecting one of the $n_i$ or other nodes).
Hence $P(n+1)$ Also holds.

• 1) $P(3) is even more trivially true ;) -- 2) A bit care is needed when fusioning: Two connected vertices may have common neighbours. With two or more common neighbourts we are done, but one common neighbour is possible. Jul 29 '13 at 16:44 • @HagenvonEitzen 1) I failed to find a simple graph of degree 3 with only 3 nodes ;) 2) you are right, if they have common neighbours we have to remove some "double" edges, but it doesn't change the proof. Was that the problem or am I missing something? – wece Jul 29 '13 at 16:49 • You are right - we have to remove at most one double edge, so$f$will still have degree at least$3$. But the original common neighbour may have fallen below degree$3\$. So we should look for an edge not part of a triangle of degree 3 nodes. If no such exists, we can fusion all three nodes of such a triangle Jul 29 '13 at 17:00
• @HagenvonEitzen Edited I hope it patch my mistake :) Thanks for your remark. It seemed to easy before ...
– wece
Jul 29 '13 at 17:20
• Thanks wece and Hagen Von Eitzen. I learned a lot. Jul 29 '13 at 19:28