+1 vote
318 views

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?

edited | 318 views
0
Can someone help me with definition of component?
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.
0

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

0
minimum of 14 vertices?
0
i did not read the word connected :(
0
I'm getting 27 What's the ans given??
0
@utkarsh

I think the question is "let G be a simple graph with 7 components".
0

Dhillu exactly i feel the same this question is framed incorrectly

0
27 vertices ??
0

A connected graph cannot have more than 1 component

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

Mk Utkarsh

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
if G is a disconnected graph then ans would be 19.
0
I have edited the question.
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.

0

Soumya Tiwari with simple disconnected graph its possible

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?

0
oops :) yes!
0
i am getting 27 ??

correction after @shaik masthan comment : correct answer is 33
+1
0
thanks @shailk masthan

+1 vote