Perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of E, such that every vertex in V is adjacent to exactly one edge in M. A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs:
15 (number)26-fullerene graphAlspach's conjectureApollonian networkAutomorphisms of the symmetric and alternating groupsBaranyai's theoremBipartite double coverBipartite graphBirkhoff algorithmBirkhoff polytopeBivariegated graphBoxicityBrauer algebraBregman–Minc inequalityChristofides algorithmCircuit rankClaw-free graphCombinatorial Geometry in the PlaneComplete bipartite graphComplete graphComponent (graph theory)Computing the permanentContinuous-time quantum walkCrispin Nash-WilliamsCrown graphCubic graphCycle decomposition (graph theory)Cycle double coverDaniel KráľDavid SumnerDeficiency (graph theory)Double factorialDulmage–Mendelsohn decompositionEar decompositionEdge coloringEdge coverEdmonds matrixExact coverFKT algorithmFactor-critical graph
Link from a Wikipage to another Wikipage
primaryTopic
Perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of E, such that every vertex in V is adjacent to exactly one edge in M. A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs:
has abstract
In graph theory, a perfect mat ...... s also called factor-critical.
@en
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,025,275,331
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
subject
comment
In graph theory, a perfect mat ...... consider the following graphs:
@en
label
Perfect matching
@en