Documentation

Mathlib.Combinatorics.SimpleGraph.Matching

Matchings #

A matching for a simple graph is a set of disjoint pairs of adjacent vertices, and the set of all the vertices in a matching is called its support (and sometimes the vertices in the support are said to be saturated by the matching). A perfect matching is a matching whose support contains every vertex of the graph.

In this module, we represent a matching as a subgraph whose vertices are each incident to at most one edge, and the edges of the subgraph represent the paired vertices.

Main definitions #

TODO #

def SimpleGraph.Subgraph.IsMatching {V : Type u_1} {G : SimpleGraph V} (M : G.Subgraph) :

The subgraph M of G is a matching if every vertex of M is incident to exactly one edge in M. We say that the vertices in M.support are matched or saturated.

Equations
  • M.IsMatching = ∀ ⦃v : V⦄, v M.verts∃! w : V, M.Adj v w
Instances For
    noncomputable def SimpleGraph.Subgraph.IsMatching.toEdge {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} (h : M.IsMatching) (v : M.verts) :
    M.edgeSet

    Given a vertex, returns the unique edge of the matching it is incident to.

    Equations
    Instances For
      theorem SimpleGraph.Subgraph.IsMatching.toEdge_eq_of_adj {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} {v : V} {w : V} (h : M.IsMatching) (hv : v M.verts) (hvw : M.Adj v w) :
      h.toEdge v, hv = s(v, w), hvw
      theorem SimpleGraph.Subgraph.IsMatching.toEdge.surjective {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} (h : M.IsMatching) :
      theorem SimpleGraph.Subgraph.IsMatching.toEdge_eq_toEdge_of_adj {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} {v : V} {w : V} (h : M.IsMatching) (hv : v M.verts) (hw : w M.verts) (ha : M.Adj v w) :
      h.toEdge v, hv = h.toEdge w, hw
      theorem SimpleGraph.Subgraph.IsMatching.map_ofLE {V : Type u_1} {G : SimpleGraph V} {G' : SimpleGraph V} {M : G.Subgraph} (h : M.IsMatching) (hGG' : G G') :
      theorem SimpleGraph.Subgraph.IsMatching.sup {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} {M' : G.Subgraph} (hM : M.IsMatching) (hM' : M'.IsMatching) (hd : Disjoint M.support M'.support) :
      (M M').IsMatching
      theorem SimpleGraph.Subgraph.IsMatching.iSup {V : Type u_1} {G : SimpleGraph V} {ι : Type u_2} {f : ιG.Subgraph} (hM : ∀ (i : ι), (f i).IsMatching) (hd : Pairwise fun (i j : ι) => Disjoint (f i).support (f j).support) :
      (⨆ (i : ι), f i).IsMatching
      theorem SimpleGraph.Subgraph.IsMatching.subgraphOfAdj {V : Type u_1} {G : SimpleGraph V} {v : V} {w : V} (h : G.Adj v w) :
      (G.subgraphOfAdj h).IsMatching
      theorem SimpleGraph.Subgraph.IsMatching.coeSubgraph {V : Type u_1} {G : SimpleGraph V} {G' : G.Subgraph} {M : G'.coe.Subgraph} (hM : M.IsMatching) :
      def SimpleGraph.Subgraph.IsPerfectMatching {V : Type u_1} {G : SimpleGraph V} (M : G.Subgraph) :

      The subgraph M of G is a perfect matching on G if it's a matching and every vertex G is matched.

      Equations
      • M.IsPerfectMatching = (M.IsMatching M.IsSpanning)
      Instances For
        theorem SimpleGraph.Subgraph.IsMatching.support_eq_verts {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} (h : M.IsMatching) :
        M.support = M.verts
        theorem SimpleGraph.Subgraph.isMatching_iff_forall_degree {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} [(v : V) → Fintype (M.neighborSet v)] :
        M.IsMatching vM.verts, M.degree v = 1
        theorem SimpleGraph.Subgraph.IsMatching.even_card {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} [Fintype M.verts] (h : M.IsMatching) :
        Even M.verts.toFinset.card
        theorem SimpleGraph.Subgraph.isPerfectMatching_iff {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} :
        M.IsPerfectMatching ∀ (v : V), ∃! w : V, M.Adj v w
        theorem SimpleGraph.Subgraph.isPerfectMatching_iff_forall_degree {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} [(v : V) → Fintype (M.neighborSet v)] :
        M.IsPerfectMatching ∀ (v : V), M.degree v = 1
        theorem SimpleGraph.Subgraph.IsPerfectMatching.even_card {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} [Fintype V] (h : M.IsPerfectMatching) :
        theorem SimpleGraph.Subgraph.IsMatching.induce_connectedComponent {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} (h : M.IsMatching) (c : G.ConnectedComponent) :
        (M.induce (M.verts c.supp)).IsMatching
        theorem SimpleGraph.Subgraph.IsPerfectMatching.induce_connectedComponent_isMatching {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} (h : M.IsPerfectMatching) (c : G.ConnectedComponent) :
        (M.induce c.supp).IsMatching
        theorem SimpleGraph.ConnectedComponent.even_card_of_isPerfectMatching {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} [Fintype V] [DecidableEq V] [DecidableRel G.Adj] (c : G.ConnectedComponent) (hM : M.IsPerfectMatching) :
        Even (Fintype.card c.supp)
        theorem SimpleGraph.ConnectedComponent.odd_matches_node_outside {V : Type u_1} {G : SimpleGraph V} {M : G.Subgraph} [Fintype V] [DecidableEq V] {u : Set V} {c : (.deleteVerts u).coe.ConnectedComponent} (hM : M.IsPerfectMatching) (codd : Odd (Nat.card c.supp)) :
        wu, ∃ (v : (.deleteVerts u).verts), M.Adj (v) w v c.supp