2
$\begingroup$

Let $G$ be an undirected graph with $n$ nodes. Prove that any two of the following implies the third:

  1. $G$ is connected
  2. $G$ is acyclic
  3. $G$ has $n-1$ edges

Proving $1, 2 \implies 3$

A connected, acyclic graph is a tree. Each node(vertex), except the root, in the tree has exactly one edge going upwards(towards the root), hence it has $n-1$ edges.

The Problem

I'm not able to write a formal proof for the other two. The problem is that here I used the fact that connected, acyclic graph is a tree and then it was easy to prove using properties of a tree, for the other I tried using contradiction but couldn't prove them.

Any hint on how to approach this problem and how to prove $1, 2 \implies 3$ without using the fact that connected acyclic graph is a tree?

Reference

This problem is from Chapter 3 of Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley

$\endgroup$
3
$\begingroup$

Proving 2,3 implies 1: We have an acyclic graph $G=(V, E)$ with $n-1$ edges. We want to prove that $G$ is a connected graph. Assume for the sake of contradiction that $G$ is not connected. This means we have $d>1$ connected components, $G=\{\bigcup_{i=1}^{d}G_i\}$.

Since $G$ is acyclic, each connected component is a tree by definition. Let $V_i$ be the set of vertices of graph $G_i$. Then, the number of edges in $G_i$ is $\mid E_i \mid = \mid V_i \mid - 1$. Thus, the total number of edges in $G$ is $\mid\ E \mid\ =\sum_{i=1}^{d}\mid E_i \mid =\sum_{i=1}^{d} (\mid V_i \mid-1)=\sum_{i=1}^{d}(\mid V_i \mid)- d = n - d < n -1$.

The last inequality follows because $d > 1$. This is a contradiction that $\mid\ E \mid\ = n-1$.

Proving that 1,3 implies 2: We have a connected graph $G=(V, E)$ with with $n-1$ edges. We want to prove that $G$ is acyclic. I will not write the proof, but I will hint that (one of many possible proofs) you can use induction on the number of vertices. And let your assumption be that given $G$ with $n-1$ vertices and at most $n-2$ edges, then $G$ is acyclic.

$\endgroup$
1
  • $\begingroup$ Thanks @Elie, I'm able to prove 1,3 implies 2 using induction :) $\endgroup$
    – atin
    Apr 12 at 12:05

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.