Nonadjacent Thin Edges in Simple Braces
Abstract
A bipartite graph $G[A,B]$ is a brace if either the underlying simple graph of $G$ is one of the complete bipartite
graphs $K_2$ and $K_{2,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'\in A$ and $b,b'\in B$. An edge $e$ of $G$ is thin if the graph $\widehat{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.
Published
2026-11-20
How to Cite
Feng, X., Lucchesi, C. L., Yan, W., & Zhou, J. (2026). Nonadjacent Thin Edges in Simple Braces. The Electronic Journal of Combinatorics, 33(4), #P4.38. https://doi.org/10.37236/13866
Article Number
P4.38