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.
 A: 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.

