Answers are grounded in this paper and cite their sources.
A bipartite graph $G[A,B]$ is a brace if either the underlying simple graph of G is one of the complete bipartitegraphs K₂ and K2,2, or G has at least six vertices and $G-a-a'-b-b'$ has a perfect matching, for every four distinct vertices a,a'∈ A and b,b'∈ B. An edge e of G is thin if the graph G-e, obtained from $G-e$ by repeatedly bicontracting vertices of degree two, is a brace. In this paper, we prove that each simple brace of order six or more contains at least two nonadjacent thin edges, thereby solving a problem posed by Carvalho, Lucchesi and Murty.
No takes yet. Share an insight, caveat, or question.
Feng et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: