Skip to content

Graph theory def: Matching number #34959

@SnirBroshi

Description

@SnirBroshi

Matchings in simple graphs exist as SimpleGraph.Subgraph.IsMatching.

I suggest we're missing the following def for the matching number of a simple graph:

noncomputable def matchingNumber (G : SimpleGraph V) : ℕ∞ :=
  ⨆ (M : G.Subgraph) (_ : M.IsMatching), M.edgeSet.encard

and basic API for it.

Metadata

Metadata

Assignees

Labels

help-wantedThe author needs attention to resolve issuest-combinatoricsCombinatorics

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions