[proofplan] We give a deterministic breadth-first search algorithm that attempts to assign each vertex one of two colours. On each connected component, an arbitrary uncoloured starting vertex receives colour $0$, and every newly discovered neighbour receives the opposite colour. If the algorithm ever finds an edge whose endpoints already have the same colour, it rejects; otherwise the resulting colour classes form a bipartition. The search inspects each vertex and each adjacency-list entry only a bounded number of times, so the running time is polynomial in the input length. [/proofplan] [step:Define the deterministic two-colour search algorithm] Let the input be an encoding $\langle G\rangle$ of a finite simple undirected graph $G = (V,E)$, where $V$ is the finite vertex set and $E \subseteq \{\{u,v\} : u,v \in V,\ u \neq v\}$ is the edge set. Define a partial colour function \begin{align*} c: V \to \{0,1\} \end{align*} during the computation; initially $c$ is undefined at every vertex. The algorithm processes the vertices in the order in which they occur in the input encoding. When it reaches a vertex $s \in V$ for which $c(s)$ is undefined, it sets $c(s) := 0$ and initializes a first-in-first-out queue $Q$ with the single element $s$. While $Q$ is nonempty, it removes the front vertex $v \in Q$ and scans every neighbour $w \in V$ with $\{v,w\} \in E$. If $c(w)$ is undefined, it sets \begin{align*} c(w) := 1 - c(v) \end{align*} and appends $w$ to $Q$. If $c(w)$ is already defined and $c(w) = c(v)$, the algorithm rejects. If all queue searches finish without rejection, the algorithm accepts. [/step] [step:Show that any rejection certifies non-bipartiteness] Suppose the algorithm rejects while scanning an edge $\{v,w\} \in E$. At that moment $c(v)$ and $c(w)$ are both defined and satisfy $c(v) = c(w)$. For each connected component search, define the root $s \in V$ to be the first vertex from that component selected by the outer loop. Define the search level function \begin{align*} \ell_s: C_s \to \mathbb{N} \cup \{0\} \end{align*} as follows: $C_s \subseteq V$ is the connected component containing $s$, and $\ell_s(x)$ is the length of the first path from $s$ to $x$ produced by the breadth-first search when $x$ is first coloured. By construction of the algorithm, every vertex $x \in C_s$ coloured in this search satisfies \begin{align*} c(x) \equiv \ell_s(x) \pmod{2}. \end{align*} When the rejecting edge $\{v,w\}$ is scanned, both endpoints lie in the same connected component $C_s$ for the root $s$ of that search. The equality $c(v)=c(w)$ implies that $\ell_s(v)$ and $\ell_s(w)$ have the same parity. Let $P_v$ be the search-tree path from $s$ to $v$, and let $P_w$ be the search-tree path from $s$ to $w$. Removing the common initial segment of $P_v$ and $P_w$, then adding the edge $\{v,w\}$, gives a cycle whose length has parity \begin{align*} \ell_s(v) + \ell_s(w) + 1 \equiv 1 \pmod{2}. \end{align*} Thus $G$ contains an odd cycle. A bipartite graph has no odd cycle, because every edge in a bipartition crosses from one colour class to the other, so any closed walk alternates colour at each step and must have even length. Therefore a rejecting computation can occur only when $G$ is not bipartite. [guided] We prove that rejection is a mathematically valid certificate, not merely a failure of the chosen colouring procedure. Suppose the algorithm rejects while scanning an edge $\{v,w\} \in E$. By the rejection rule, both endpoints have already been assigned colours and the colours agree: \begin{align*} c(v) = c(w). \end{align*} Fix the root $s \in V$ of the breadth-first search that coloured these vertices. Let $C_s \subseteq V$ denote the connected component of $G$ containing $s$. Define \begin{align*} \ell_s: C_s \to \mathbb{N} \cup \{0\} \end{align*} by letting $\ell_s(x)$ be the length of the search-tree path from $s$ to $x$ at the moment $x$ is first coloured. The root has $\ell_s(s)=0$ and colour $c(s)=0$. Whenever a vertex $w$ is first discovered from a previously coloured vertex $v$, the algorithm sets $c(w)=1-c(v)$, so the colour flips exactly once along each search-tree edge. Hence, by induction along the search-tree path from $s$ to $x$, every coloured vertex $x \in C_s$ satisfies \begin{align*} c(x) \equiv \ell_s(x) \pmod{2}. \end{align*} Apply this to the rejecting edge $\{v,w\}$. Since $c(v)=c(w)$, the integers $\ell_s(v)$ and $\ell_s(w)$ have the same parity. Let $P_v$ be the search-tree path from $s$ to $v$, and let $P_w$ be the search-tree path from $s$ to $w$. These two paths share an initial segment from $s$ to their last common vertex. Delete that common initial segment from both paths, then traverse the remaining part of $P_v$ to $v$, cross the edge $\{v,w\}$, and traverse the remaining part of $P_w$ backwards to the last common vertex. This produces a cycle. Its length has the same parity as $\ell_s(v)+\ell_s(w)+1$, because the common initial segment is counted twice before deletion and therefore contributes an even number. Since $\ell_s(v)$ and $\ell_s(w)$ have the same parity, this length is odd: \begin{align*} \ell_s(v) + \ell_s(w) + 1 \equiv 1 \pmod{2}. \end{align*} Thus rejection produces an odd cycle in $G$. A bipartite graph cannot contain an odd cycle: if $V=A \cup B$ is a bipartition with $A \cap B=\varnothing$, every edge alternates between $A$ and $B$, so a closed walk returning to its starting side must use an even number of edges. Therefore any graph rejected by the algorithm is not bipartite. [/guided] [/step] [step:Show that acceptance produces a bipartition] Suppose the algorithm accepts. Define two subsets of $V$ by \begin{align*} V_0 = \{v \in V : c(v)=0\} \end{align*} and \begin{align*} V_1 = \{v \in V : c(v)=1\}. \end{align*} Every vertex is eventually processed by the outer loop, so every vertex is coloured. Hence $V = V_0 \cup V_1$, and the definitions give $V_0 \cap V_1 = \varnothing$. Let $\{u,v\} \in E$ be any edge. When the endpoint $u$ is removed from the queue in the component search containing this edge, the algorithm scans the neighbour $v$. Since the algorithm accepts, it never encounters a scanned edge whose endpoints have equal colours. Therefore $c(u) \neq c(v)$, so one endpoint lies in $V_0$ and the other lies in $V_1$. Thus every edge of $G$ crosses between $V_0$ and $V_1$, and $(V_0,V_1)$ is a bipartition of $G$. [/step] [step:Bound the running time by a polynomial] Let $n = |V|$ and $m = |E|$. In an adjacency-list encoding, each vertex is inserted into a queue at most once, because a vertex is inserted only when its colour changes from undefined to defined. Each removed vertex has its adjacency list scanned once. Since $G$ is undirected, the total number of adjacency-list entries scanned is $2m$. Therefore the total search time is \begin{align*} O(n+m). \end{align*} The input length is at least proportional to $n+m$ for an adjacency-list encoding, and for any standard graph encoding the operations of reading vertices and enumerating neighbours are polynomial in the input length by hypothesis. Hence the deterministic algorithm runs in polynomial time. [/step] [step:Conclude membership in $\mathrm{P}$] The algorithm is deterministic, halts on every finite graph encoding, accepts exactly the bipartite graphs by the correctness steps above, and runs in time polynomial in the input length. Therefore the language $\mathrm{BIPARTITE}$ is decided by a polynomial-time deterministic algorithm, so \begin{align*} \mathrm{BIPARTITE} \in \mathrm{P}. \end{align*} [/step]