Bipartite graph

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

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 — The complete vertex and edge sets are explicit.
• Subset — The two parts are subsets of the vertex set.
• 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.