Let Gbe an acyclic graph with c components. Show that the number of edges of G is n − c.

Question

Let   Gbe an acyclic graph with   c components. Show that the number of edges of   G is   n  −  c.

smh3402en · Accepted Answer

We can prove the result prove by using introduction on   n,the number of vertices.The answer is obviously true for   n  =  1  ,  2  ,  3. Let be the answer true for all trees with fewer than   n vertices. Let   T be a tree with   n vertices and let be   e an edge with end vertices   u and   v. So the only path between   u and   v is   e. Therefore deletion of   e from   T disconnects   T. Now   T  −  e consists of exactly two components       T          1       and       T          2       say, and as there were no cycles tp begin with, each component is a tree. Let       n          1        &amp;lt;  n and       n          2        &amp;lt;  n. Thus by induction hypothesis, number of edges in       T          1       and       T          2       are respectively       n          1        −  1 and       n          2        −  1. Hence the number of edges in   T  =      n          1        −  1  +      n          2        −  1  +  1  =      n          1        +      n          2        −  1  =  n  −  1

Let G be an acyclic graph with c components. Show that the number of edges of G is n−c.

Answered question

Answer & Explanation

New Questions in High school geometry