[Math] Prove that any circuit contains a cycle

discrete mathematicsgraph theoryintuition

This is a practice question (not HW)

Prove that any circuit in a graph must contain a cycle AND that any circuit that is not a cycle contains at least two cycles.

Note : This is for a first course in Graph theory

I have answer to this question but the answer raises more questions.
ANSWER: Suppose the vertices of the circuit are $v_0,v_1,…v_n,v_0$. Consider all subcircuits of the form $v_i,…v_n,v_i$. The subcircuit that uses the fewest number of vertices is a cycle (my Q: BUT WHY).

Best Answer

Suppose this smallest circuit $C$ is not a cycle. Then it must repeat a vertex $v_j$. So write the circuit as $v_i C v_j C v_j C v_i$ (that is, follow the cycle from $v_i$ to $v_j$ around back to $v_j$ and back to $v_i$).

$v_j C v_j$ is a smaller circuit, contradicting the choice of $C$.

Your approach to the proof was correct: you just needed to look for a contradiction. The combination of looking for a graph satisfying some minimal or maximal property together with a proof by contradiction is extremely powerful in graph theory.

Related Solutions

[Math] Graph Theory: How do we know Hamiltonian Path exists in graph where every vertex has degree ≥3

Here's an example of a connected $3$-regular graph with no Hamiltonian path. Let $H_1,H_2,H_3$ be three vertex-disjoint copies of $K_4$. For each $i\in\{1,2,3\}$ choose an edge $e_i$ of $H_i$ and subdivide it, making the midpoint of $e_i$ into a new vertex $x_i$. Finally, take a new vertex $y$ and add edges $x_1y,x_2y,x_3y$. This connected $3$-regular graph on $16$ vertices does not have a Hamiltonian path, because removing the vertex $y$ breaks it into three components.

[Math] Which of the following graphs has an Eulerian circuit

Here is a $2$-regular graph that is not connected:

             o---o   o---o  
             |   |   |   |  
             o---o   o---o

Your reasoning about (b) and (c) is correct; (c) is the only one that must have an Euler circuit.

Best Answer

Related Solutions

[Math] Graph Theory: How do we know Hamiltonian Path exists in graph where every vertex has degree ≥3

[Math] Which of the following graphs has an Eulerian circuit

Related Question