# Bipartite graph

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

A finite undirected simple graph is bipartite when all vertices split into two disjoint parts and every edge crosses between the parts.

mko-bipartite-graph · definition · v0.10.0



## Mathematical statement

Check complete vertex coverage, disjointness of the two parts and every edge crossing. A failed proposed partition does not prove nonbipartiteness; an odd cycle can certify it. Isolated vertices may belong to either part, and whether empty parts are allowed must be explicit.





## Representative formula (exact TeX)

B(G)





## Assumptions


- The graph is complete, finite, undirected, loop-free and simple.
- This slice allows an empty part in an edgeless graph, while still covering every vertex.





## Symbol scope


- B — bipartite graph
- G — finite simple graph





## Intuition, definition, and misconceptions

The parts are disjoint and their union is V.

The endpoints of every edge belong to different parts.

An odd cycle certifies nonbipartiteness; one failed proposed partition does not.

Do not omit isolated vertices, infer nonbipartiteness from a single failed partition, or require nonadjacent vertices to have different colors.





## Adopted derivation guide

[A bipartition certificate with an isolated vertex](https://ocme.evemisslab.com/en/derivations/derivation-mko-bipartite-graph-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Finite simple undirected graphs](https://ocme.evemisslab.com/en/mko/mko-graph/) — The complete vertex and edge sets are explicit.
- [Subset](https://ocme.evemisslab.com/en/mko/mko-subset/) — The two parts are subsets of the vertex set.
- [Function mapping](https://ocme.evemisslab.com/en/mko/mko-function-mapping/) — A two-color assignment is an equivalent representation.





## Verification boundary

Only finite undirected simple graphs are handled; directed-graph extensions are not inferred.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add matchings and bipartite-graph theorems.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/bipartite-graph.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-bipartite-graph/index.md)