4
$\begingroup$

I'm trying to prove

A graph with an equal number of edges and vertices contains a cycle as a subgraph

My attempt

Induction on the number of vertices:

Clearly holds for $n=3$

Assume true for all graphs on $\le n-1$ vertices.

For n:

Case 1: There is a vertex of degree 1, say $v$. Then $G = v \cup H$. By hypothesis, H contains a cycle, so G necessarily contains a cycle.

Case 2: No vertex of degree 1. So every vertex has degree $\ge 2$. Take minimum spanning tree of G, which contains no cycles and has at most $n-1$ edges. But our hypothesis says that any graph on $\le n-1$ edges contains a cycle. Contradiction.

I'm not sure about my case 2, any verification would be helpful.

$\endgroup$
4
$\begingroup$

Your proof is incorrect. A spanning tree exists if and only if the graph is connected. $deg(u) \ge 2 \not\implies G$ is connected. You haven't proved that the graph is connected.

Example: Consider this graph with 6 nodes and 6 edges: $1-2 , 2-3 , 3-1 , 4-5 , 5-6 , 6-1$

Hint 1:

Try to use the inductive hypothesis on each connected component of the graph.

Hint 2:

Use the fact that a connected component with $r$ number of nodes must have $\ge r-1$ edges.

Hint 3:

Use the fact that the sum of the edges of all connected components must be equal to $n$, the number of nodes in the graph.

Hint 4:

If there are $r \ge 1$ connected components, then the total number of edges in these connected components is $ m \ge n - r$. But we know that $m = n$ which implies that at least one connected component with $l$ number of nodes has more than $l-1$ edges. Now use the inductive hypothesis.

$\endgroup$
  • 2
    $\begingroup$ I must complement you on your username :P $\endgroup$ – user230452 Mar 28 '16 at 15:49
2
$\begingroup$

There are a couple of problems with your argument. First, as Banach Tarski pointed out, $G$ doesn’t contain a spanning tree unless it’s connected. Secondly, the non-existence of vertices of degree $1$ in $G$ does not imply that every vertex of $G$ has degree at least $2$: $G$ may have isolated vertices, vertices of degree $0$. Finally, your induction hypothesis is that each graph on fewer than $n$ vertices with as many edges as vertices contains a cycle; it does not say that a graph with $n-1$ edges has a cycle unless that graph has $n-1$ vertices, which yours does not. Thus, your attempt to apply your induction hypothesis is invalid. An induction argument is nonetheless possible; I suggest one possibility below.

HINT: Suppose first that $G$ is not connected, and let the components of $G$ be $G_1,\ldots,G_m$. For $k=1,\ldots,m$ let $n_k$ be the number of vertices of $G_k$ and $e_k$ the number of edges.

  • Explain why $e_k\ge n_k-1$ for $k=1,\ldots,m$.
  • Show that there must be a $k\in\{1,\ldots,m\}$ such that $e_k\ge n_k$, and explain why that $G_k$ must contain a cycle.

Now suppose that $G$ is connected. Then $G$ has a spanning tree $T$. Let $e=uv$ be the edge of $G$ that is not in $T$, and explain how to construct a cycle in $G$ that contains the edge $e$.

$\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.