{"id":"arxiv/2610.07733","url":"https://arxiv.org/abs/2610.07733","tags":["math.CO"],"score":0,"title":"The maximum size of simple solid matching covered graphs","domain":"math.CO","source":"arxiv","authors":["Tong Zhang","Wei Li"],"reviews":0,"subject":"math.CO","summary":"A connected graph with at least two vertices is matching covered if each of its edges is contained in a perfect matching. A matching covered graph is solid if every separating cut in it is a tight cut. A matching covered graph which is free of nontrivial tight cuts is a brick if it is nonbipartite. Every bipartite matching covered graph is solid. Lucchesi and Murty conjectured that there exists a positive integer $N$ such that, for every integer $n\\ge N$, the maximum number of edges in a simple solid matching covered graph on $2n$ vertices is $n^2$. In this paper, we disprove this…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-06","reactions":{}}