If a -regular graph on vertices has a maximum matching of size , its unmatched vertices are independent. Counting their incident edges gives , and hence .
The disjoint union of triangles is -regular on vertices and has matching number , attaining the regular-graph lower bound .
Articles by others on the same topic
There are currently no matching articles.