Codex Wiki
OurBigBook.com
Site
Source code
Regular-graph matching bound from unmatched vertices
Home
Mathematics
Area of mathematics
Foundations of mathematics
Graph theory
Matching in a graph
OurBigBook.com
Words: 58
Articles: 1
If a
k
-regular graph on
n
vertices has a maximum matching of size
m
, its unmatched vertices are independent. Counting their incident edges gives
k
(
n
−
2
m
)
≤
2
(
k
−
1
)
m
, and hence
m
≥
kn
/
(
4
k
−
2
)
.
Table of contents
58
1
Disjoint union of triangles as a sharp matching example
Regular-graph matching bound from unmatched vertices
25
Ancestors
(6)
Matching in a graph
Graph theory
Foundations of mathematics
Area of mathematics
Mathematics
Home