λ-matchability in cubic graphs

Basic Information

• Paper ID: 2505.12823
• Title: λ-matchability in cubic graphs
• Authors: Santhosh Raghul, Nishad Kothari (IIT Madras)
• Classification: math.CO (Combinatorics)
• Publication Date: October 15, 2025
• Paper Link: https://arxiv.org/abs/2505.12823

Abstract

This paper investigates λ-matchability in 2-connected cubic graphs. For a vertex v in a 2-connected cubic graph G, v is called λ-matchable if there exists a spanning subgraph of G such that v has degree 3 while all other vertices have degree 1. The quantity λ(G) denotes the number of such vertices. Since λ = 0 in bipartite graphs, the authors similarly define the concept of λ-matchable pairs, denoted ρ(G). The paper improves constant lower bounds on λ and ρ recently established by Chen, Lu, and Zhang, utilizing matching-theoretic parameters originating from Lovász's pioneering work, and characterizes all tight examples. Additionally, it resolves a problem posed by Chen, Lu, and Zhang: characterizing all 2-connected cubic graphs satisfying λ = n.

Research Background and Motivation

1. Problem Background: λ-matchability is an important concept in matching theory. In 2-connected cubic graphs, a vertex is λ-matchable if and only if there exists a spanning subgraph where that vertex has degree 3 and all other vertices have degree 1. This concept is closely related to perfect matchings but provides finer granularity.
2. Problem Significance:
   • λ-matchability has fundamental theoretical importance in graph theory, relating to graph connectivity, matching covers, and other key concepts
   • This concept has been used by other researchers to prove that 2-connected cubic graphs have at least n/2 perfect matchings
   • It is valuable for understanding structural properties of cubic graphs
3. Limitations of Existing Methods:
   • Chen, Lu, and Zhang (2025) established constant lower bounds on λ and ρ, but these bounds are not tight
   • Lack of complete structural characterization of graphs achieving the bounds
   • The characterization problem for graphs with λ = n remains unsolved
4. Research Motivation: To improve existing bounds, provide tighter bounds and completely characterize tight examples, while resolving the outstanding characterization problem.

Core Contributions

1. Improved Lower Bounds: Using matching-theoretic parameters β(G) and β'(G) from Lovász theory, the authors establish stronger bounds λ(G) ≥ β(G) and ρ(G) ≥ β'(G) + 3b'(G) - 3
2. Complete Characterization of Tight Examples:
   • For the λ bound: equality holds if and only if β(G) = n_nonbip(G)
   • For the ρ bound: provides characterizations at two different levels of tightness
3. Resolution of Open Problem: Completely characterizes 2-connected cubic graphs satisfying λ(G) = n(G), constructing a recursively defined graph family N'
4. Theoretical Framework: Establishes a systematic extension method from 3-connected to 2-connected graphs, using decomposition theory as an inductive tool

Methodology Details

Task Definition

λ-matchable vertex: For a vertex v in a 2-connected cubic graph G, v is λ-matchable if there exists a spanning subgraph M of G such that d_M(v) = 3 and d_M(u) = 1 for all u ≠ v.

λ-matchable pair: For a connected bipartite cubic graph HA,B, a pair (a,b) with a ∈ A, b ∈ B is λ-matchable if there exists a spanning subgraph M such that d_M(a) = d_M(b) = 3 and all other vertices have degree 1.

Core Theoretical Tools

1. Parity Lemma: For a graph G, if X is a subset of vertices where each member has odd degree, then |∂(X)| ≡ |X| (mod 2)
2. Brick and Brace Decomposition:
   • Brick: a non-bipartite matching-covered graph with no non-trivial tight cuts
   • Brace: a bipartite matching-covered graph with no non-trivial tight cuts
   • Every matching-covered graph admits a unique decomposition into bricks and braces
3. Key Parameter Definitions:
   • β(G): the sum of vertex counts of all bricks in G
   • β'(G): ∑(n(H)/2)², where H ranges over all braces of order ≥ 6 in G
   • b'(G): the number of braces of order ≥ 6 in G

Main Technical Methods

1. Tight Cut Analysis: Utilizing properties of tight cuts, decomposing problems to smaller graphs via cut-contraction operations
2. Obstruction Theory: Using obstruction concepts from Tutte's theorem to characterize non-λ-matchable vertices
3. Splicing Operations: Constructing graph families with specific properties by splicing 3-connected graphs
4. Inductive Proof Strategy:
   • For 3-connected graphs: using tight cuts as inductive tools
   • For 2-connected graphs: using 2-cut decomposition as inductive tools

Main Theorems

Theorem 1.18 (Lower Bound for λ in 3-Connected Graphs)

Every 3-connected cubic graph G satisfies λ(G) ≥ β(G). Furthermore:

• If G is bipartite, then λ(G) = β(G) = 0
• If G is non-bipartite, then λ(G) = β(G) if and only if β(G) = n(G)

Theorem 1.22 (Lower Bound for ρ in 3-Connected Bipartite Graphs)

Every 3-connected bipartite cubic graph H satisfies: ρ(H) ≥ β'(H) + 3b'(H) - 3 ≥ 3n(H) - 9

Theorem 1.26 (Extension to 2-Connected Graphs)

Every 2-connected cubic graph G satisfies λ(G) ≥ β(G), with equality if and only if β(G) = n_nonbip(G)

Structural Characterization Results

Complete Characterization of λ = n

Definition of Graph Family N': A 2-connected cubic graph G' belongs to N' if and only if every 3-connected piece of G' satisfies the corresponding recursive conditions.

Theorem: A 2-connected cubic graph G satisfies λ(G) = n(G) if and only if G ∈ N'.

This resolves the open problem posed by Chen, Lu, and Zhang.

Technical Innovations

1. Parametric Approach: Introduction of parameters β(G) and β'(G), providing more precision than previous constant bounds
2. Decomposition Theory Application: Systematic use of Lovász's tight cut decomposition theory
3. Constructive Characterization: Providing not only existence results but also explicit construction methods
4. Unified Framework: Establishing a unified treatment framework from 3-connected to 2-connected graphs

Experimental Results

As this is a pure theory paper, the main results are mathematical theorem proofs. The paper verifies theoretical results through numerous examples:

1. Tightness of Bounds: Constructs infinite graph families achieving the bounds
2. Completeness of Characterization: Verifies that all small-order graphs conform to the characterization results
3. Counterexample Construction: Demonstrates that certain possible generalizations do not hold

Related Work

1. Foundational Theory: Built upon Lovász's (1987) matching theory
2. Direct Predecessors: Improves results of Chen, Lu, Zhang (2025)
3. Application Context: Related to work by Král, Sereni, Steibitz on the number of perfect matchings
4. Methodology: Employs brick theory from Edmonds, Lovász, and Pulleyblank

Conclusions and Discussion

Main Conclusions

1. Establishes improved lower bounds on λ and ρ using matching-theoretic parameters
2. Completely characterizes the structure of tight examples
3. Resolves the characterization problem for graphs with λ = n
4. Provides a systematic theoretical framework

Limitations

1. Results primarily apply to cubic graphs; generalization to arbitrary graphs requires further work
2. Certain bounds are not as tight for general 2-connected graphs as for 3-connected cases
3. While construction methods are explicit, computational complexity is high

Future Directions

1. Generalization to more general regular graphs
2. Investigation of algorithmic aspects of λ-matchability
3. Exploration of relationships with other graph parameters

In-Depth Evaluation

Strengths

1. Theoretical Depth: Skillful application of deep matching-theoretic tools
2. Completeness of Results: Not only improves bounds but completely characterizes tight examples
3. Systematic Methodology: Establishes a general framework for handling such problems
4. Proof Techniques: Clear inductive proof structure with refined technical handling

Weaknesses

1. Scope of Applicability: Primarily limited to cubic graphs
2. Computational Complexity: Algorithmic aspects are not discussed
3. Practical Applications: Strong theoretical orientation with limited practical application value

Impact

1. Theoretical Contribution: Provides new perspectives and tools for matching theory
2. Methodological Value: Decomposition methods may be applicable to other graph-theoretic problems
3. Completeness: Resolves an important open problem in the field

Applicable Scenarios

Primarily applicable to foundational research in graph theory, particularly in matching theory and structural analysis of regular graphs. Also valuable for applications requiring understanding of the fine structure of cubic graphs.

References

The paper cites key literature in the field, including:

• Lovász's foundational work in matching theory
• Direct predecessor work by Chen, Lu, Zhang
• Bondy-Murty's graph theory textbook
• Lucchesi-Murty's monograph on matching theory

This paper represents high-quality theoretical work in combinatorial mathematics. Through elegant mathematical techniques, it improves important bounds on graph-theoretic parameters and provides complete structural characterizations. While its practical applications are limited, its theoretical value is substantial, laying the foundation for further research in related areas.