betaFeedback

WorksMathematics

Characterization of Cubic Graphs with Exactly Two Lonely Edges

Abstract

Perfect matchings are fundamental to understanding structural connectivity in cubic graphs, with "lonely edges" (edges in exactly one perfect matching) forming a critical underexplored class. Goedgebeur et al. (J. Graph Theory, 112 (2026) 276-289) established an upper bound of 6 on the number of lonely edges in 3-connected non-double covered cubic graphs and completely characterized the classes Uk\mathcal{U}_k for 3≤k≤63 \le k \le 6. Narayana et al. subsequently gave a recursive characterization of the subclass in which the two lonely edges lie in the same perfect matching. This paper completes the classification by presenting a full structural characterization of U2\mathcal{U}_2, the family of 3-connected cubic graphs with exactly two lonely edges. We identify the minimally non-contractible "primitive kernels" of U2\mathcal{U}_2 and develop constructive operations to generate any graph in U2\mathcal{U}_2 from these kernels.

Introduction

A perfect matching is an edge set in which every vertex is incident with exactly one edge. Perfect matchings have played a central role in graph theory since the late nineteenth century, with applications in combinatorial optimization, coding theory, and network design. In particular, for cubic graphs, perfect matchings provide an important tool for studying structural connectivity and resilience.

A fundamental theorem of Petersen states that every bridgeless cubic graph has a perfect matching [7]. Schönberger subsequently proved the corresponding edgewise statement: every edge of a bridgeless cubic graph belongs to at least one perfect matching [9]. Thus, for cubic graphs, bridgelessness is equivalent to the property that every edge belongs to some perfect matching. These results established the basic connection between bridges and perfect-matching coverage.

Later research turned from the existence of perfect matchings to their number and distribution. Esperet et al. proved that the number of perfect matchings in a bridgeless cubic graph grows exponentially with the order of the graph [1]. This result motivates studying the multiplicity with which individual edges occur in perfect matchings. A cubic graph is called matching double covered if every edge belongs to at least two distinct perfect matchings. Consequently, edges that occur in exactly one perfect matching form a natural exceptional class. Goedgebeur et al. introduced the term lonely edge for an edge that belongs to exactly one perfect matching and initiated a systematic study of non-double-covered cubic graphs [5]. Their work builds on an earlier result of Esperet et al., who proved that every 3-connected cubic graph is matching double covered unless it belongs to a special class of graphs called Klee graphs [2].

Klee graphs are defined recursively by starting with K4K_4 and replacing vertices by triangles. Fiorini and Wilson conjectured that Klee graphs are precisely the planar cubic graphs with a unique 3-edge-colouring, and a proof of this conjecture was given in Fowler’s doctoral thesis [3, 4]. Not every Klee graph is non-double covered. For example, the truncation of K4K_4 is still matching double covered. Thus, a more precise structural analysis is needed to identify exactly which Klee graphs contain lonely edges.

Goedgebeur et al. reduced the study of bridgeless non-double-covered cubic graphs to their 3-connected components by means of 2-cut reductions [5]. Within the resulting 3-connected setting, they developed a constructive framework based on vertex-to-triangle replacements and spanning subgraph joins. For k≥1k \ge1, let Uk\mathcal{U}_k denote the subclass of graphs in this framework having exactly kk lonely edges. Several cases were settled in their work. They proved that no graph in the considered class has more than six lonely edges and that Uk=∅\mathcal{U}_k = \varnothing for k>6k > 6. Moreover, they also characterized the classes with three, four, five and six lonely edges [5]. In addition, they exhibited infinite families in U1\mathcal{U}_1 and U2\mathcal{U}_2, showing that the cases with at least three lonely edges and those with one or two lonely edges have substantially different structural behaviour. For example, graphs in U1\mathcal{U}_1 and U2\mathcal{U}_2 can contain arbitrarily many triangles, whereas those in U3,U4,U5,U6\mathcal{U}_3,\mathcal{U}_4,\mathcal{U}_5,\mathcal{U}_6 contain at most three triangles, except for K4K_4, which contains four triangles. Recently, Narayana et al. gave a recursive characterization of the subclass in which the two lonely edges lie in the same perfect matching.

The present paper focuses on the class U2\mathcal{U}_2 of 3-connected non-double-covered cubic graphs with exactly two lonely edges. The main objective is to give a complete structural characterization of this class. We address the following two questions.

  1. Which graphs in U2\mathcal{U}_2 are minimally non-contractible to a smaller graph in U2\mathcal{U}_2? We call such graphs primitive U2\mathcal{U}_2 kernels.

  2. Given an arbitrary graph G∈U2G \in\mathcal{U}_2, can GG be obtained from a primitive kernel by a finite sequence of expansions, while every intermediate graph remains in U2\mathcal{U}_2?

The first question is answered in Section 3, where we classify all primitive U2\mathcal{U}_2 kernels. The second question is addressed in Section 4, where we introduce standard markings and prove that the relevant zero-loss expansions preserve membership in U2\mathcal{U}_2. Together, these results provide a constructive characterization of every graph in U2\mathcal{U}_2 from a primitive kernel.

Preliminaries

Throughout this paper, all graphs are assumed to be finite, simple, and cubic unless explicitly stated otherwise. Our work builds directly upon the framework established in [5]; we therefore adopt most of the notation and conventions introduced therein, with only minor modifications made to simplify subsequent discussions. For the sake of completeness and readability, we restate key definitions below.

Let NG(v)={x,y,z}N_G(v) = \{x,y,z\}. When vv is replaced by a triangle, label the three new vertices vxv_x, vyv_y, vzv_z, where vxv_x is adjacent to the old neighbor xx, vyv_y to yy, and vzv_z to zz. Add the three triangle edges vxvyv_xv_y, vyvzv_yv_z, vzvxv_zv_x. The opposite edge of the old edge vxvx is vyvzv_yv_z. This labeling depends only on the old neighbors in the current step, so every operation is completely determined at the vertex-label level. A join rooted at vv is a spanning subgraph JJ of GG such that dJ(v)=3d_J(v)=3 and dJ(u)=1d_J(u)=1 for every u≠vu\ne v, where dJ(v)d_J(v) represents the degree of vv in JJ. Since GG is cubic, JJ necessarily contains all three edges incident with vv.

Definition 2.1. A graph GG is a Klee-graph if G=K4G=K_4 or there exists a Klee-graph HH and a vertex w∈V(H)w\in V(H) such that G=HwG=H^w. We denote the set of Klee-graphs by K\mathcal{K}.

Let G∈KG\in\mathcal{K}. Suppose that a graph HH can be obtained from GG through a finite sequence of vertex expansion operations, where each operation replaces a single vertex with a triangle. In such cases, we refer to HH as a descendant of GG. Building on this parent-descendant framework, we further define a direct hierarchical relationship: for any vertex v∈V(G)v\in V(G), the graph GvG^v obtained by expanding vv into a triangle is called a child of GG, and conversely, GG is called the parent of GvG^v. Let M(G)\mathcal{M}(G) denote the set of perfect matchings of GG. An edge ee is called a lonely edge if it belongs to exactly one member of M(G)\mathcal{M}(G). Put

L(G)={e∈E(G):∣{M∈M(G):e∈M}∣=1},ℓ(G)=∣L(G)∣.L(G)=\{e\in E(G):|\{M\in\mathcal{M}(G):e\in M\}|=1\},\qquad\ell(G)=|L(G)|.

Write

Uk={G∈K:ℓ(G)=k},U=⋃k≥1Uk.\mathcal{U}_k=\{G\in\mathcal{K}:\ell(G)=k\},\qquad\mathcal{U}=\bigcup_{k\ge1}\mathcal{U}_k.

Definition 2.2. For G∈UG\in\mathcal{U} and v∈V(G)v\in V(G), define

ΣG(v)={e∈L(G):v∉V(e), and there exists a join rooted at v that contains e}.\Sigma_G(v)=\{e\in L(G):v\notin V(e),\text{ and there exists a join rooted at }v\text{ that contains }e\}.

We simultaneously define a vertex vv satisfying ΣG(v)=∅\Sigma_G(v)=\varnothing as a zero-loss expansion vertex, or alternatively refer to such a vertex as zero-loss expandable.

Lemma 2.3. Let xy∈L(G)xy\in L(G) and v∉{x,y}v\notin\{x,y\}. Then xy∈ΣG(v)xy\in\Sigma_G(v) if and only if

{x,y}∩NG[v]=∅andG−NG[v]−{x,y} has a perfect matching.\{x,y\}\cap N_G[v]=\varnothing\quad\text{and}\quad G-N_G[v]-\{x,y\}\text{ has a perfect matching}.

Proof. If JJ is a join rooted at vv containing xyxy, then JJ contains all three edges incident with vv. Hence every vertex in N(v)N(v) already has degree 11 in JJ, so neither xx nor yy lies in N[v]N[v]. After deleting N[v]∪{x,y}N[v]\cup\{x,y\}, the remaining edges of JJ are pairwise disjoint and cover all remaining vertices, and therefore form a perfect matching.

Conversely, suppose that {x,y}∩N[v]=∅\{x,y\}\cap N[v]=\varnothing and that MM is a perfect matching of G−N[v]−{x,y}G-N[v]-\{x,y\}. Then M∪{xy}∪{vw:w∈N(v)}M\cup\{xy\}\cup\{vw:w\in N(v)\} is a join rooted at vv containing xyxy. This proves both directions.

Let NG(v)={x,y,z}N_G(v)=\{x,y,z\}. Define the transfer map on lonely edges by

λv(e)={e,v∉V(e),vavb,e=vc where {a,b,c}={x,y,z}.\lambda_v(e)= \begin{cases} e, & v\notin V(e),\\ v_av_b, & e=vc\text{ where }\{a,b,c\}=\{x,y,z\}. \end{cases}

The following result is the set-valued form of [5 Lemma 3.5 and Corollary 3.6].

Proposition 2.4. Let G∈UG\in\mathcal{U} and v∈V(G)v\in V(G). Then

L(Gv)={λv(e):e∈L(G)∖ΣG(v)}.(1)L(G^v)=\{\lambda_v(e):e\in L(G)\setminus\Sigma_G(v)\}. \tag*{(1)}

and

ℓ(Gv)=ℓ(G)−∣ΣG(v)∣.(2)\ell(G^v)=\ell(G)-|\Sigma_G(v)|. \tag*{(2)}

Corollary 2.5. If G∈UkG \in\mathcal{U}_k, then Gv∈U2G^v \in\mathcal{U}_2 if and only if ∣ΣG(v)∣=k−2|\Sigma_G(v)| = k - 2.

Corollary 2.6. Let G∈UG \in\mathcal{U} and NG(v)={x,y,z}N_G(v) = \{x,y,z\}. Then {vxx,vyy,vzz}∩L(Gv)=∅\{v_{xx},v_{yy},v_{zz}\} \cap L(G^v) = \varnothing.

Proof. Let ww be an arbitrary vertex in {x,y,z}\{x,y,z\}. If vw∈L(G)vw \in L(G), then, by Proposition 2.4, wvw∉L(Gv)wvw \notin L(G^v). Otherwise, vw∉L(G)vw \notin L(G). Then vwvw is contained in at least two perfect matchings of GG. Let MvwM_{vw} and Mvw′M'_{vw} be two distinct perfect matchings of GG containing vwvw. Then Mvw−vw+wvw+eM_{vw} - vw + wv_w + e, Mvw′−vw+wvw+eM'_{vw} - vw + wv_w + e are two distinct perfect matchings of GvG^v, where ee denotes the edge opposite vwvw. Hence, wvw∉L(Gv)wv_w \notin L(G^v). Combining the above, we obtain {vxx,vyy,vzz}∩L(Gv)=∅\{v_{xx},v_{yy},v_{zz}\} \cap L(G^v) = \varnothing.

Definition 2.7. A graph C∈U2C \in\mathcal{U}_2 is called a primitive U2\mathcal{U}_2 kernel if, for every triangle TT of CC, C/T∉U2C/T \notin\mathcal{U}_2, where C/TC/T is the cubic graph obtained by contracting TT to a single vertex.

Definition 2.8. For a graph family A⊆U2\mathcal{A} \subseteq\mathcal{U}_2, let Neu⁡(A)\operatorname{Neu}(\mathcal{A}) be the smallest family satisfying:

  • (a) A⊆Neu⁡(A)\mathcal{A} \subseteq\operatorname{Neu}(\mathcal{A});

  • (b) if G∈Neu⁡(A)G \in\operatorname{Neu}(\mathcal{A}) and ΣG(v)=∅\Sigma_G(v) = \varnothing, then Gv∈Neu⁡(A)G^v \in\operatorname{Neu}(\mathcal{A}).

References

  1. [1]L. Esperet, F. Kardoš, D. Král, A. D. King, and S. Norine, Exponentially many perfect matchings in cubic graphs, Advances in Mathematics 227 (2011), 1646–1664. https://doi.org/10.1016/j.aim.2011.03.015.
  2. [2]L. Esperet, D. Král, P. Škoda, and R. Škrekovski, An improved linear bound on the number of perfect matchings in cubic graphs, European Journal of Combinatorics 31 (2010), 1316–1334. https://doi.org/10.1016/j.ejc.2009.11.008.
  3. [3]S. Fiorini and R. J. Wilson, Edge colourings of graphs, in L. W. Beineke and R. J. Wilson (eds.), Selected Topics in Graph Theory, Chapter 5, pp. 103–126, Academic Press, New York, 1978.
  4. [4]T. G. Fowler, Unique coloring of planar graphs, PhD thesis, Georgia Institute of Technology, 1998.
  5. [5]J. Goedgebeur, D. Mattiolo, G. Mazzuoccolo, J. Renders, and I. H. Wolf, Cubic graphs with edges in exactly one perfect matching, Journal of Graph Theory 112 (2026), 276–289. https://doi.org/10.1002/jgt.70024.
  6. [6]D. V. V. Narayana, D. Mattiolo, K. Gohokar, and N. Kothari, Solitude patterns of r-graphs via CLM’s dependence relation, arXiv:2409.00534v3 (2026). https://arxiv.org/abs/2409.00534v3.
  7. [7]J. Petersen, Die Theorie der regulären Graphen, Acta Mathematica 15 (1891), 193–220. https://doi.org/10.1007/BF02392606.
  8. [8]Z. Qian and P. Li, Verification Supplement for Characterization of Cubic Graphs with Exactly Two Lonely Edges, version 1.0.1 with the manuscript-numbering update, computer software, 2026. Commit: 55415fb255b37b526dea5c24599b563c71f64857. https://github.com/QZw-05/python/tree/55415fb255b37b526dea5c24599b563c71f64857.arxiv.org/abs/2611.20843
  9. [9]T. Schönberger, Ein Beweis des Petersenschen Graphensatzes, Acta Scientiarum Mathematicarum (Szeged) 7 (1934), 51–57.

Paper details

vlnc:W_6d7hvrp4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents