The Gateway to Computer Science Excellence
+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?

 

in Graph Theory by Junior
edited by | 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.

Please explain anyone.
0

Soumya Tiwari with simple disconnected graph its possible

0

@Utkarsh Joshi 

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 ??

if it is wrong please someone update answer

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

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,890 answers
201,084 comments
118,128 users