An independent set of vertices in a graph is a subset of the vertices in which no two elements are adjacent. The vertex independence number $\operatorname{ind}_V(G)$ of $G$ is the cardinality of the largest independent set in $G$. Examples: 1. In simple graphs, singleton sets are independent. 2. What is the largest number of bishops one can place on an $n\times n$ board such that no two pairs attack one another? Let $G=(V,E)$ be the (undirected) graph where $V$ = the set of all $n^2$ squares and $\{u,v\}\in E$ iff a bishop on $u$ would attack a bishop on $v$ (i.e. $u,v$ lie on the same diagonal). Then a set of squares admits a non-attacking bishop placements precisely when it is an independent set in $G$. Thus the number of interest is $\text{ind}_{V}(G)$. See [[Non-attacking bishops problem|solution]]: Note that, $G$ is the [[Line Graphs|line graph]] of the bipartite graph $H=(U \cup W, \mathcal{E})$ where: $U$ is the set of NE-SW diagonals; $W$, the set of NW-SE diagonals; and $\{ D, F \}\in \mathcal{E}$ iff $D$ and $F$ intersect so that $\mathcal{E}$ is represent the set of $n^2$ squares. So the independence number of $G$ is the same of the matching number of $H$ which by, [[König-Egevàry Theorem (Size of Maximum Matching of Bipartite Graph Equals Size of Minimum Vertex Cover)|König's theorem]] is the same as the size of minimum vertex cover of $H$. # Properties A [[Clique (in graphs)]] is an independent set in $G^C$. Thus $\text{ind}_{V}(G)=\text{clique}(G^C)$. # Bibliography 1. https://en.wikipedia.org/wiki/Independent_set_(graph_theory)