edited by
549 views
1 votes
1 votes

The number of independent sets in a complete graph with n vertices is ____

edited by

2 Answers

1 votes
1 votes
i think the answer should be n.
Since every vertex is adjacent to every other vertices in a complete graph,the graph is n-colorable.
Now the graph can be partitioned into n sets with each set containing exactly one vertex and holding a color for that vertex.Now each partition with 1 vertex is an independent set ...Hence number of independent sets in a complete graph of n vertices is n
0 votes
0 votes
It should be 0 since there won't be any pairwise disjoint vertices in a complete graph.

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
0 answers
2
Pavan Kumar Munnam asked May 12, 2017
391 views
algorithm to find more than one path between any two vertices of a graph G=(V,E) , with a complexity of O(VE) ?
3 votes
3 votes
3 answers
3
Vicky rix asked Apr 7, 2017
1,442 views
A graph consists of only one vertex,which is isolated ..Is that graphA) a complete graph ???B) a clique???C) connected graph ???Please explain your answer ...
0 votes
0 votes
1 answer
4