A graph is 2-colourable iff it has no odd closed walk
ProvedFamousTheorems.two_colorable_iff_no_odd_cycle_6bA graph is 2-colourable iff it has no odd closed walk. A graph is bipartite, that is, properly -colourable, if and only if every closed walk in has even length.
This is Kőnig's characterization of bipartite graphs, usually stated as "no odd cycles": a closed walk of odd length contains an odd cycle. It shows that bipartiteness can be tested by breadth-first search. Bipartite graphs are the setting of Kőnig's and Hall's theorems on matchings.
Formalization note. Mathlib's SimpleGraph.two_colorable_iff_forall_loop_even. G.Colorable 2 says that there is a proper colouring with two colours, and G.Walk u u is the type of closed walks at . The graph may be infinite.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem two_colorable_iff_no_odd_cycle_6b {α : Type*} {G : SimpleGraph α} : G.Colorable 2 ↔ ∀ (u : α) (w : G.Walk u u), Even w.length := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `SimpleGraph.two_colorable_iff_forall_loop_even`. Proof here reduces to that Mathlib result.