1
$\begingroup$

I am looking for an error in the proof but I am not certain about it. Pretty sure it has something to do with how there is not always a cycle of length 3.

Theorem 1. For every (undirected) graph $G = (V; E)$ without loops, if $|V| \ge 3$ and for every vertex has a degree of at least $2$, there exists a cycle of length $3$.

Proof. We proceed by induction on $|V|$. As a base case, consider $|V| = 3$. For any graph on three vertices, if all vertices have degree $2$, then every vertex is connected to both other vertices. Thus there is always a cycle of length $3$. To prove the inductive step, let $G$ be a graph with $k$ vertices, and construct a new graph $G_0$ on $k + 1$ vertices by adding one new vertex to $G$ and $2$ edges incident to the new vertex. Since $G$ has $k$ vertices, by the inductive hypothesis it has a cycle of length $3$. Thus the graph $G_0$ contains the same cycle of length $3$. This completes the proof.

$\endgroup$
  • $\begingroup$ What is jV j? Can you edit to clarify? $\endgroup$ – ml0105 Mar 26 '14 at 1:50
1
$\begingroup$

The way you proceed in your inductive proof doesn't work. Not every graph (of your form) can be constructed in that manner. As in mlo105's answer, $C_4$ is a counterexample: you can't make $C_4$ by starting with a $3$-cycle and adding a vertex and two edges (which is the only kind of $4$-vertex graph your method can create).

In general, when you're doing an inductive proof in graph theory, you usually start with a graph on $k+1$ vertices and somehow reduce it to the case of a graph with $k$ vertices - not the other way around.

$\endgroup$
2
$\begingroup$

The theorem is incorrect. If I give you $C_{4}$, a cycle on four vertices, each vertex has a degree of at least two. However, there is no cycle of length $3$ in $C_{4}$.

$\endgroup$
1
$\begingroup$

You're assuming the new vertex is not on one of the edges of G.

$\endgroup$

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.