The Gateway to Computer Science Excellence

+1 vote

Let G be a connected graph with 7 ** connected **components and each component is a tree. If G has 26 edge then number of vertices in G is?

0

Assume each component is having n1,n2,n3,n4,n5,n6,n7 vertices.

Since each component is a tree,

n1-1 + n2-1 + n3-1 + n4-1 + n5-1 + n6-1 + n7-1= 26.

n1+n2+n3+n4+n5+n6+n7=19.

Since each component is a tree,

n1-1 + n2-1 + n3-1 + n4-1 + n5-1 + n6-1 + n7-1= 26.

n1+n2+n3+n4+n5+n6+n7=19.

0

bhai connected graph can only have one component as per https://proofwiki.org/wiki/Definition:Component_of_Graph

0

give small example for explanation

This Graph is weakly connected graph

4 component : {1,2} {3 ,2} , {3,4} , {5,4}

0

Magma I'm still unable to figure out where i'm wrong

Graph G is connected and contain 26 edges now

Question mentions there are 7 components

Now i checked 3-4 sources for definition and i found that a disconnected graph can have more than one components

0

yeah you're right...question is wrong..it's unable to find the no of vertices

But what I'm say that...the example that I Upload above "That graph is weakly connected graph and also have 4 components "

0

@mk utkarsh

*"A simple graph with n vertices and k components can have at most [(n-k)(n-k+1)]/2 edges." *

0

Dhillu Thambi yes i know that

v = 6, k = 2

now make a a complete graph of 5 edges will have 10 edges

another component is isolated vertex

**so you see graph is not connected.**

and plug both values in your formula you'll get 10 as answer

0

@Utkarsh With Connected graph it's not possible as it has only one component.But if it's simple graph then also it's not possible I'm unable to get this point.

Please explain anyone.

Please explain anyone.

0

n1-1 + n2-1 + n3-1 + n4-1 + n5-1 + n6-1 + n7-1= 26.

n1+n2+n3+n4+n5+n6+n7=19.

it is 26+7 = 33, right?

52,218 questions

59,890 answers

201,084 comments

118,128 users