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

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.