12
$\begingroup$

How to prove this question? If a graph with $n$ vertices and $n$ edges it must contain a cycle?

$\endgroup$
3
  • 1
    $\begingroup$ Am I right to assume that you mean a cycle? $\endgroup$
    – dreamer
    Jun 8 '13 at 14:16
  • $\begingroup$ I'm guessing he means "contains a cycle". I misread it first. $\endgroup$
    – mrf
    Jun 8 '13 at 14:21
  • $\begingroup$ Sometimes circle is used to mean cycle (as noted on Wikipedia (ref.)), but I think this is rare. $\endgroup$ Jun 14 '13 at 13:29
17
$\begingroup$

Assume that $G$ contains no cycles. Then every connected component of $G$ is a tree.

Claim The number of edges in a tree on $n$ vertices is $n-1$.

Proof is by induction. The claim is obvious for $n=1$. Assume that it holds for trees on $n$ vertices. Take a tree on $n+1$ vertices. It's an easy exercise (look at a longest path in $G$) to show that a tree has at least one terminal vertex (i.e. with degree $1$). Removing this terminal vertex along with its edge, we get a tree on $n$ vertices, and induction takes us home.

Hence the number of edges in a graph without cycles is $n-k$, where $k$ is the number of connected components.

$\endgroup$
1
$\begingroup$

Here's is an approach which does not use induction:

Let $G$ be a graph with $n$ vertices and $n$ edges. Keep removing vertices of degree $1$ from $G$ until no such removal is possible, and let $G'$ denote the resulting graph. Note that in each removal, we're removing exactly $1$ vertex and $1$ edge, so $G'$ cannot be empty, otherwise before the last removal we'd have a graph with $1$ vertex and $1$ edge, and $G'$ has the same number of vertices and edges. Therefore the minimum degree in $G'$ is at least $2$, which implies that $G'$ has a cycle.

$\endgroup$
1
  • 2
    $\begingroup$ How is that "not using induction"? $\endgroup$
    – mrf
    Mar 21 '19 at 15:32
0
$\begingroup$

Here's another approach:

Let $P = a_1, a_2, \dots, a_n$ be a simple path of maximal length in G.

Since the degree of each vertex is greater than two, there exists a vertex $b$ such that ${b,a_1}$ is an edge.

Now, there can be two cases:

  1. $b$ is on the path P: In this case, the sub-path from $a_1$ to $b$ and the edge from $b$ to $a_1$ forms a cycle.

  2. $b$ is not on the path P: In this case, the path $b,a_1,a_2, \dots, a_n$ is a path of greater length than $P$, thus contradicting our assumption.

Source

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