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$ is the set of all $n^2$ squares and $\{u,v\}\in E$ if and only if 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 placement of bishops if and only if it is an [[Independent set of vertices (in graphs)|independent set]] in $G$. Thus the number of interest is $\text{ind}_{V}(G)$, the maximum size of an independent set of vertices in $G$ - known as its vertex independence number. Observe 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 in bijection with the set of $n^2$ squares. By [[König-Egevàry Theorem (Size of Maximum Matching of Bipartite Graph Equals Size of Minimum Vertex Cover)|König’s theorem]], in _any_ bipartite graph the size of a maximal matching (its *matching number*) equals the size of a minimal vertex cover (a vertex cover here is a set of diagonals that touches every square). So the maximum bishops you can place equals the smallest number of diagonals needed to “cover” all squares. Any vertex cover must have at least $2n-2$ diagonals: since no two of the $n-1$ leftmost squares on the top and bottom ranks lie on the same diagonal. Furthermore, it is easy to see that you can cover all squares with $2n-2$ diagonals. So the matching number of $H$ is $2n-2$.