The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
What is the vertex connectivity and edge connectivity of complete graph?

Is it n or n-1?
asked in Graph Theory by Veteran (17.4k points)
edited by | 163 views

1 Answer

+4 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

answered by Active (2.2k points)
selected by

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

28,946 questions
36,792 answers
34,689 users