ProofAtlas

Graph theory · formal theorem

König’s Edge-Coloring Theorem

Every finite bipartite simple graph admits a proper edge coloring using its maximum degree many colors.

Lean proofpassed
Unfinished proof stepsNone
Formal resultAccepted
König edge-coloring statement mapThe edges of a finite bipartite simple graph split into maximum-degree many matchings, which serve as color classes.
Exact scope: Every finite bipartite simple graph admits a proper edge coloring with its maximum degree many colors.

Line counts exclude blank lines; comments and documentation count. The total is the commit-pinned first-party Lean import closure; Mathlib and other third-party dependencies are excluded.

The theorem at a glance

König’s edge-coloring theorem at a glance

Editorial graph-theory poster explaining why Delta colors suffice for every finite bipartite simple graph through matching extraction and induction.
A matching covering every maximum-degree vertex can be removed to lower Δ and supply one color class.

Accessible transcript

finite bipartite G ⇒ proper edge coloring with Δ(G) colors

Hall-style counting produces an injective adjacent selector on maximum-degree vertices. Finite selector paths yield a covering matching; deleting it lowers the maximum degree, after which induction colors the remainder and one fresh color restores the matching.

Read the complete poster transcript

GRAPH THEORY · BIPARTITE MATCHINGS

KÖNIG’S EDGE-COLORING THEOREM

Δ(G) COLORS SUFFICE

FOR EVERY FINITE BIPARTITE SIMPLE GRAPH G

Incident edges receive different colors.

EACH COLOR CLASS IS A MATCHING

HOW THE PROOF MOVES

1 · SELECT NEIGHBORS OF MAXIMUM-DEGREE VERTICES

Hall-style counting gives an injective adjacent selector.

2 · EXTRACT A COVERING MATCHING

Finite selector paths resolve collisions and cover every maximum-degree vertex.

3 · DELETE ONE MATCHING

The maximum degree drops by at least one.

4 · COLOR RECURSIVELY

Color the remainder, then give the deleted matching one fresh color.

EXACT SCOPE

Finite bipartite simple graphs. Existence only:

no algorithm, list-edge-coloring, multigraph, or non-bipartite claim.

Theorem schematic

Color bipartite edges with Δ colors

A finite bipartite graph whose edges are separated into Delta matching colors so no incident edges share a color.
Every finite bipartite simple graph has a proper edge coloring using at most its maximum degree Δ colors.

χ′(G) ≤ Δ(G) for finite bipartite simple G

König’s edge-coloring theorem decomposes the edge set of a finite bipartite simple graph into at most Δ matchings, which serve as the color classes.

Proof architecture

How matchings peel a bipartite graph into colors

5 curated stages

The checked proof obtains an injective adjacent selector on maximum-degree vertices, turns its finite path components into a matching that covers every such vertex, deletes that matching to lower the maximum degree, and colors recursively before assigning one fresh color.

These source-anchored stages explain the retained proof route. They are not an extracted Lean proof-term dependency graph.

  1. A representative bipartite graph with every maximum-degree source paired to a distinct adjacent target.
    Neighborhood counting supplies distinct adjacent targets for all maximum-degree vertices.
    01

    Hall counting gives an injective neighbor selector

    |S| ≤ |N(S)| ⇒ injective selector

    For every finite set of maximum-degree vertices, degree counting gives at least as many available neighbors. The resulting Hall inequalities produce one injective adjacent selector on the full maximum-degree set.

    Lean lemmas for this step
    • card_le_card_biUnion_neighborFinset_of_forall_degree_eq_maxDegree
    • exists_injective_neighbor_of_maxDegree_vertices
  2. A repetition-free selector path alternates between the two shores and ends outside the maximum-degree source set.
    Injectivity and finiteness turn an unhit source into a path ending outside the source set.
    02

    Follow a selector path to its first exit

    unhit source → finite selector path → first exit

    When the selector range is not contained in the maximum-degree set, start at a source that is not selected by any other source and iterate the selector. No vertex repeats before the first exit, and alternating path edges begin the covering matching.

    Lean lemmas for this step
    • exists_unselected_source_of_not_range_subset
    • selector_path_ne_of_lt
    • exists_first_iterate_exit_of_unselected
    • exists_isMatching_cover_of_selector_path
  3. Representative finite selector paths alternate across two bipartite shores and contribute nonconflicting selected edges.
    Finite selector paths and components choose compatible edges that cover the required vertices without collisions.
    03

    Resolve selector components into a matching

    selector components ⇒ covering matching

    Following selector arrows in the finite bipartite graph produces paths and cycles. Choosing alternating edges component by component removes selector collisions and yields one matching covering all maximum-degree vertices.

    Lean lemmas for this step
    • selector_path_ne_of_lt
    • exists_isMatching_cover_of_selector_path
    • exists_isMatching_cover_subset_of_injective_neighbor
    • exists_isMatching_cover_maxDegree_vertices_of_bipartite
  4. A representative bipartite graph before and after one highlighted matching is removed, with maximum degree reduced by one.
    Deleting the matching removes one edge at every maximum-degree vertex and cannot increase any other degree.
    04

    Delete the covering matching

    Δ(G ∖ M) ≤ Δ(G)−1

    Every former maximum-degree vertex loses an incident edge, while all other vertices had degree below Δ already. The remainder is bipartite and has maximum degree at most Δ−1.

    Lean lemmas for this step
    • edgeColorable_of_isMatching_sdiff
    • degree_sdiff_of_le
    • maxDegree_sdiff_spanningCoe_le_pred_of_isMatching_cover
    • isBipartiteWith_sdiff
  5. A representative bipartite graph with the remainder colored recursively and the removed matching restored in one new color.
    Use Δ−1 colors on the remainder and one fresh color for every edge of the deleted matching.
    05

    Color recursively and restore one fresh color

    (Δ−1) colors + 1 matching color = Δ colors

    Induction colors the smaller-degree remainder. Because the deleted edges form a matching, they may all receive one fresh color without creating a conflict, completing a proper coloring with Δ colors.

    Lean lemmas for this step
    • konigEdgeColoringTheorem_of_matching_cover
    • edgeColorable_of_isMatching_sdiff
    • ProperEdgeColoring
    • konigEdgeColoringTheorem

Exact formal proposition

Hypotheses and conclusion

theorem konigEdgeColoringTheorem : KonigEdgeColoringStatement

Result boundary

What this page does—and does not—establish

Every finite bipartite simple graph admits a proper edge coloring with its maximum degree many colors.

About these visual explanations

These AI-generated visuals explain the theorem and proof route; they are not proof evidence. Their publication review was completed separately from review of the formal result. The exact Lean proposition and checked source remain authoritative.

Continue the mathematics

Start from the complete checked source

The pinned theorem and its complete local import closure let internal and external agents inspect the proof, compare an alternate route, isolate reusable lemmas, or formulate a stronger exact statement. Lean checks every proposed extension against its exact formal statement.

The ZIP contains the checked first-party Lean import closure, exact statements and boundaries, license, notice, evidence, source-footprint manifest, and an agent continuation file. Mathlib and other third-party dependencies are not bundled.

Checked source + agent continuation package · 1 Lean file · 1 evidence record · Download ZIPBrowse the checked source onlineDownload main Lean fileDownload checker evidence (JSON)Download Apache-2.0 license
Formal-result publication and review details

Independent publication review

The formal theorem's publication gates are accepted

Lean checks the proof. Independent AI review separately accepted evidence completeness, statement alignment, result boundary, and the retained theorem wording. Those gates apply to the formal result; generated media is reviewed and promoted separately. Neither review replaces Lean's proof check or broadens the theorem.

01

Formal evidence

Independent review accepted the recorded build, exact declarations, unfinished-step scan, and axiom evidence.

02

Statement alignment

The formal declaration was accepted against the named theorem and its exact variant.

03

Result boundary

The accepted boundary keeps nearby stronger or commonly confused claims out of scope.

04

Public wording

Independent review accepted the retained theorem explanation and source presentation. Generated media follows a separate review and promotion gate.

05

Canonical source

The first-party source link is pinned to the checked package commit and exact Lean file.

06

Accepted result

A validated accepted-result record binds the four reviews to the checked formalization.

Expanded visual

Open original image in a new tab