edited by
18,179 views
57 votes
57 votes

If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have?

  1. $\left\lfloor\frac {n}{k}\right\rfloor$
  2. $\left\lceil \frac{n}{k} \right\rceil$
  3. $n-k$
  4. $n-k+1$
edited by

11 Answers

0 votes
0 votes
Suppose, if each vertex is a component, then k=n, then there will not be any edges among them.

Now, replace the same concept in options,
Option 1 and 2: Both will give answer 1. (i.e. one edge among them) which is false.
Option 3: n-k = 0 edges.
Option 4: n-k+1 : 1 edge, which is false.
0 votes
0 votes

Answer : C

A forest is an undirected graph in which any two vertices are connected by at most one path .

Image result for forest graph theory

so, no. of edges in this forest graph = x

|v| = 6  , |k| = 1

x = |v|-|k| = 5

0 votes
0 votes

Answer : C

A forest is an undirected graph in which any two vertices are connected by at most one path .

Image result for forest graph theory

so, no. of edges in this forest graph = x

|v| = 6  , |k| = 1

x = |v|-|k| = 5

Answer:

Related questions

100 votes
100 votes
10 answers
1
38 votes
38 votes
9 answers
3
go_editor asked Sep 28, 2014
26,898 views
The maximum number of edges in a bipartite graph on $12$ vertices is____
32 votes
32 votes
9 answers
4
makhdoom ghaya asked Feb 13, 2015
24,370 views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.