PreprintarXiv licencearXiv
The maximum number of edges in minimal matching covered graphs
Abstract
A connected graph G with at least two vertices is {\em matching covered} if each of its edges lies in a perfect matching. A matching covered graph is {\em minimal} if the removal of any edge results in a graph that is no longer matching covered. Lovász and Plummer [J. Combin. Theory, Ser. B 23 (1977) 127--138] proved by ear decompositions that every minimal matching covered bipartite graph G different from K2 has at most $(3|V(G)|-6)/2$ edges, and this bound is sharp for all |V(G)|≥4. In this paper, we prove that every minimal matching covered nonbipartite graph G with at least 6 vertices has at most $5(|V(G)|-2)/2$ edges, and this bound is sharp for all |V(G)|≥6.
Related
- The maximum size of simple solid matching covered graphs
- Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
- The maximum size of intersecting k-graphs with covering number k
- Minimal Cayley graphs with large chromatic number
- The Maximum Number of Shortest Paths in Graphs
BibTeX
@misc{he2026maximum,
title = {{The maximum number of edges in minimal matching covered graphs}},
author = {Xiaoling He},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30978},
eprint = {2609.30978},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30978},
}
RIS
TY - UNPB
TI - The maximum number of edges in minimal matching covered graphs
AU - Xiaoling He
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.30978
UR - https://arxiv.org/abs/2609.30978
AB - A connected graph G with at least two vertices is {\em matching covered} if each of its edges lies in a perfect matching. A matching covered graph is {\em minimal} if the removal of any edge results in a graph that is no longer matching covered. Lovász and Plummer [J. Combin. Theory, Ser. B 23 (1977) 127--138] proved by ear decompositions that every minimal matching covered bipartite graph G different from K_2 has at most $(3|V(G)|-6)/2$ edges, and this bound is sharp for all |V(G)|≥4. In this paper, we prove that every minimal matching covered nonbipartite graph G with at least 6 vertices has at most $5(|V(G)|-2)/2$ edges, and this bound is sharp for all |V(G)|≥6.
ER -