in Graph Theory recategorized by
2,969 views
0 votes
0 votes
Is every k connected graph is k-1 connected or the reverse? I always get confused. Can someone explain with the help of an example.
in Graph Theory recategorized by
3.0k views

1 comment

i did nt get ur question
0
0

1 Answer

1 vote
1 vote
Best answer

k edge connected graph : A graph that is connected remains connected when less than k number of edges are removed is called a k edge connected graph. 
For example

According to the definition a triangle is also a 1 edge connected graph but not 3 edge connected graph because removing 2 edges will disconnect it. So, it should be "every k connected graph is also k-1 connected graph" but the reverse is not true.

Correct me if i am wrong,anyone. 
 

selected by

1 comment

Yes. Thanks.  reason is : if removing many vertices cannot disconnect the graph, then you  have no hope of disconnecting the graph by removing fewer vertices.

But this is not the only definition generally used. There are others and in those cases above conjecture is not true.

1
1

Related questions

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