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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Nonadjacent Thin Edges in Simple Braces

Cláudio Leonardo Lucchesi, Xing Feng, Weigen Yan, Jinqiu Zhou
The Electronic Journal of Combinatorics
Advanced Graph Theory Research
article

Nonadjacent Thin Edges in Simple Braces

Cláudio Leonardo Lucchesi, Xing Feng, Weigen Yan, Jinqiu Zhou
article en

Abstract

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.

The Electronic Journal of CombinatoricsVol. 33(4)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon