Lax Lean Archive

Bipartite graphs

Lax881656.Bipartite · concepts/Lax881656/Bipartite.lean · lax-881656

definition

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    A simple graph is bipartite when its vertices admit a proper coloring with two colors: adjacent vertices always receive different colors.

    Concept map
    1 concept; 1 descendant hidden
    100%
    Open claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.Combinatorics.SimpleGraph.Bipartite
    2
    3/-!
    4---
    5title: Bipartite graphs
    6type: definition
    7---
    8A simple graph is bipartite when its vertices admit a proper coloring with two
    9colors: adjacent vertices always receive different colors.
    10
    11# Formalization notes
    12
    13The predicate is stated through the canonical graph-coloring interface. For a
    14simple graph this is equivalent to a partition of the vertices into two
    15independent sets, including in the presence of isolated vertices.
    16-/
    17
    18set_option autoImplicit false
    19
    20namespace Lax881656.Bipartite
    21
    22/-- A simple graph is bipartite when it is properly colorable with two colors. -/
    23def IsBipartite {V : Type*} (G : SimpleGraph V) : Prop :=
    24 G.Colorable 2
    25
    26end Lax881656.Bipartite
    27
    Formalization notes

    The predicate is stated through the canonical graph-coloring interface. For a simple graph this is equivalent to a partition of the vertices into two independent sets, including in the presence of isolated vertices.

    Builds on

    none

    Used by
    From Mathlib

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…