GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
115 views
What is the vertex connectivity and edge connectivity of complete graph?

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

1 Answer

+2 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 (1.7k points)  
selected by


Top Users Sep 2017
  1. Habibkhan

    6960 Points

  2. Warrior

    2424 Points

  3. Arjun

    2358 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. makhdoom ghaya

    1750 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,059 questions
33,665 answers
79,739 comments
31,078 users