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

vagnhestagn

vagnhestagn

Answered question

2022-10-08

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

Answer & Explanation

smh3402en

smh3402en

Beginner2022-10-09Added 11 answers

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 < n and n 2 < 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

Do you have a similar question?

Recalculate according to your conditions!

New Questions in High school geometry

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?