recategorized by
335 views

1 Answer

Best answer
7 votes
7 votes

An independent vertex set of a graph $G$ is a subset of the vertices such that no two vertices in the subset has an edge in $G$.

 A maximum independent vertex set is an independent vertex set containing the largest possible number of vertices for a given graph. A maximum independent vertex set is not equivalent to a maximal independent vertex set, which is simply an independent vertex set that cannot be extended to a larger independent vertex set.
 
 The independence number of a graph is the cardinality of the maximum independent set.
 


In the given graph vertices $2,4,6$ and $8$ are connected to all other vertices and each of them form a maximal vertex set of size $1$ (addition of any other vertex is not possible). The maximal independence vertex set is of size (independence number) $4 - \color{magenta}{\{1,3,5,7\}}$

And there is no other independence vertex set of size $4$ which means the number of maximum independence set of the given graph is $1.$

selected by
Answer:

Related questions

2 votes
2 votes
1 answer
1
2 votes
2 votes
1 answer
2
gatecse asked Sep 14, 2020
151 views
In the graphs given below certain vertices are marked in RED. Which of the marked vertices form a vertex cover? (Mark all the appropriate choices)
1 votes
1 votes
1 answer
3
gatecse asked Sep 14, 2020
195 views
If $G$ is a simple graph with $16$ edges and $\overline{G}$ has $12$ edges, how many vertices does the complement graph $\overline{G}$ have?
4 votes
4 votes
1 answer
4
gatecse asked Sep 14, 2020
324 views
The number of possible connected simple graphs with $3$ labelled vertices is ________