Extremal graphs for average size of maximal matchings in bicyclic graphs
Finding the graph shapes that give the smallest average matchings
Mathematicians determined the minimum possible average size of maximal matchings in bicyclic graphs — networks with exactly two cycles — and identified exactly which graph shape achieves this minimum. For any such graph with n vertices, the average matching size cannot drop below (4n−11)/(2n−5), with equality occurring only when two triangles share an edge and extra vertices hang off one corner.
This completes a research program started years ago on matching problems in increasingly complex graphs. The methods used here — breaking down the problem by identifying which small matchings drive the minimum — create a template for solving similar extremal problems on other graph families, potentially accelerating progress on open questions in combinatorics.