I am in a little confusion, so here is my reasoining. For a complete graph with 5 verticies $ K_{5}, \text{ indpendent set I = } \{\varnothing,\{1\},…,\{5\}\},$ which means that independence number $\alpha(G) =|\{1\}| =1?$ But for me intuitively a complete graph has $\alpha(G)=0$ since there is NO such set on $K_{5}$ where no verticies are adjacent. Any good suggestion to clarify my confusion?
$\begingroup$
$\endgroup$
asked Aug 9, 2017 at 14:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, a complete graph has independence number $\alpha(G)=1$.
Note that an independent set $S$ of size one is the largest set of vertices you can choose without an edge between any two vertices in the set. A set without at least two vertices results in the property being vacuously true. Pick any two distinct vertices in the set $S$ - you can't, there's only one - therefore the property is satisfied. Note that it doesn't matter that the vertex in $S$ has neighbours outside of $S$ - it only matters that there are no two vertices, both in $S$, with an edge between them in the graph.
