Nonadjacent Thin Edges in Simple Braces
A bipartite graph $G[A,B]$ is a brace if either the underlying simple graph of $G$ is one of the complete bipartitegraphs $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.
Authors
- Cláudio Leonardo Lucchesi (ORCID: https://orcid.org/0000-0002-7865-8086)
- Xing Feng
- Weigen Yan
- Jinqiu Zhou
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2026-11-20
- DOI
- https://doi.org/10.37236/13866
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00