Graph Theory – Prove Graph with Nodes of Degree 3 or Higher Contains a Cycle with a Chord

Question

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.

Answer 1

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.