2
$\begingroup$

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.

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

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Jul 29 '13 at 16:44
  • $\begingroup$ @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? $\endgroup$
    – wece
    Jul 29 '13 at 16:49
  • $\begingroup$ 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 $\endgroup$ Jul 29 '13 at 17:00
  • $\begingroup$ @HagenvonEitzen Edited I hope it patch my mistake :) Thanks for your remark. It seemed to easy before ... $\endgroup$
    – wece
    Jul 29 '13 at 17:20
  • $\begingroup$ Thanks wece and Hagen Von Eitzen. I learned a lot. $\endgroup$
    – user43666
    Jul 29 '13 at 19:28

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.