# Some graph theory

graph $G$ is an ordered pair $(V,E)$ where $V$ is a finite nonempty set of vertices and $E$ is a set of two-element subsets of $V$ called edges. By convention, we write $uv$ to denote an edge $\{u,v\}\in E$. The degree of a vertex $u\in V$ is the cardinality of the set $\{v \in V: uv\in E\}$. A graph $G$ is said to be bipartite if $V=V_1\cup V_2$ where $V_1\cap V_2=\varnothing$ and $uv\in E$ implies $u\in V_1, v\in V_2$ or $v\in V_1, u\in V_2$. Time for a little theorem:

If $G$ is a graph that is not bipartite, then there exist $u,v\in V$ such that $\deg u + \deg v$ is even.

Proof: If there do not exist $u,v\in V$ such that $\deg u + \deg v$ is even, let

\begin{aligned} V_1 &= \{v\in V : \deg v \text{ is even} \}\\ V_2 &= \{v\in V : \deg v \text{ is odd} \} \end{aligned}

Then every edge in $G$ contains a vertex from $V_1$ and a vertex from $V_2$. It follows that $(V_1, V_2)$ is a bipartition of $G$, and hence that $G$ is bipartite.