The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
298 views
What is the vertex connectivity and edge connectivity of complete graph?

Is it n or n-1?
in Graph Theory by Boss (24.9k points)
edited by | 298 views
0
Extra information:

vertex connectivity <= edge connectivity <= minimum degree of graph

Example of are them being equal?

Ex : For Q3 (Cubic graph) all of them are equal.to 3,

1 Answer

+5 votes
Best answer

Its N-1 
Vertex Connectivity means minimum Number of vertices needed to be removed to disconnect the graph or make it a trivial graph 
Trivial Graph means graph with only one node 
Edge Connectivity means minimum number of edges that must be removed to disconnect the graph 
In case of complete graph min degree of any node is n-1 so you need to remove at least  n-1 edges

by Active (2.9k points)
selected by

Related questions

+7 votes
1 answer
1
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
50,362 questions
55,786 answers
192,410 comments
90,918 users