3 votes 3 votes What is the vertex connectivity and edge connectivity of complete graph? Is it n or n-1? Graph Theory discrete-mathematics graph-theory graph-connectivity + – rahul sharma 5 asked Jun 7, 2017 • edited Jun 7, 2017 by rahul sharma 5 rahul sharma 5 1.3k views answer comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Dec 19, 2017 reply Follow Share 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, 0 votes 0 votes Please log in or register to add a comment.
Best answer 6 votes 6 votes 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 aehkn answered Jun 7, 2017 • selected Jul 27, 2017 by rahul sharma 5 aehkn comment Share Follow See all 3 Comments See all 3 3 Comments reply lalitver10 commented Jan 5, 2022 reply Follow Share Hii @aehkn If we remove n-1 vertices from the graph, we left only 1 vertix in the graph and as we know single vertix graph itself is a connected graph so in case of complete graph Edge Connectivity is n-1 and vertix connectivity is not defined. 0 votes 0 votes raja11sep commented Jan 5, 2022 reply Follow Share The minimum number of vertices whose removal makes ‘G’ either disconnected or reduces ‘G’ in to a trivial graph is called its vertex connectivity. Trivial graph means a graph with single vertices, which is the case here. @lalitver10 1 votes 1 votes Psy Duck commented Feb 15, 2023 reply Follow Share @raja11sep furfect 1 votes 1 votes Please log in or register to add a comment.