Math 2.0

Combinatorics Definition

Perfect matching

Builds on Matching

Definition

Let GG be a graph. A perfect matching of GG is a matching MM such that every vertex of GG is an end of an edge of MM.

Remarks

In a perfect matching, each vertex is an end of exactly one edge of MM. Thus a finite graph with a perfect matching has an even number of vertices. Hall's theorem for bipartite graphs characterizes the bipartite graphs with a perfect matching. Tutte's theorem does this for all finite graphs. The complete graph K4K_4 has 33 perfect matchings.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Matching, definition, no evidence levelMatchingdefinitionPerfect matching, definition, no evidence levelPerfect matchingdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Matching definition
  2. Perfect matching definition

Where this leads

2 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Perfect_matching, lead section
About this page
Tag05ZPH8KF9K
URIm2://05ZPH8KF9K
Kinddefinition
WritingW1 stated
MSC05C70
DefinesPerfect matching
UsesMatching

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by

Results about this