A note on the number of non-cycle components in a pseudo 2-factor of graphs

Basic Information

• Paper ID: 2510.12155
• Title: A note on the number of non-cycle components in a pseudo 2-factor of graphs
• Author: Masaki Kashima (Keio University, Yokohama, Japan)
• Classification: math.CO (Combinatorics)
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12155

Abstract

This paper investigates the problem of counting non-cycle components in pseudo 2-factors of graphs. A pseudo 2-factor is a spanning subgraph in which each connected component is isomorphic to $K_1$, $K_2$, or a cycle. Bekkai and Kouider proved in 2009 that every graph $G$ has a pseudo 2-factor with at most $α(G)-δ(G)+1$ non-cycle components. This paper generalizes this result, proving that every graph $G$ has a pseudo 2-factor with at most $f(G)$ non-cycle components, where $f(G)$ is the maximum value of $|I|-δ_G(I)+1$ over all independent sets $I$ of $G$.

Research Background and Motivation

1. Core Problem: Investigating upper bounds on the number of non-cycle components (i.e., components isomorphic to $K_1$ or $K_2$) in pseudo 2-factors of graphs.
2. Problem Significance:
   • 2-factors are classical concepts in graph theory closely related to Hamiltonian cycles
   • Pseudo 2-factors, as a generalization of 2-factors, allow isolated vertices and edges, ensuring that every graph admits a pseudo 2-factor
   • Studying the number of non-cycle components helps understand structural properties of graphs
3. Limitations of Existing Methods:
   • The result of Bekkai and Kouider provides an upper bound of $α(G)-δ(G)+1$, but this bound may not be tight
   • Lack of refined analysis considering local structural features of graphs
4. Research Motivation: By introducing the function $f(G)$ that considers local degree information of all independent sets, obtain tighter upper bounds and unify several known results.

Core Contributions

1. Main Theorem: Proves that every graph $G$ has a pseudo 2-factor with at most $\max\{0, f(G)\}$ non-cycle components, where $f(G) = \max\{|I| - δ_G(I) + 1 \mid I \text{ is an independent set of } G\}$
2. Theoretical Unification: This result simultaneously generalizes:
   • The result of Bekkai and Kouider on pseudo 2-factors (Theorem 1)
   • The result of Niessen on 2-factor existence (Theorem 2)
   • The author's previous result on 2-factor existence (Theorem 3)
3. Tightness of Bounds: Proves that the new upper bound is optimal by constructing specific examples demonstrating the tightness
4. Magnitude of Improvement: Through concrete examples, demonstrates that the gap between $f(G)$ and $α(G)-δ(G)+1$ can be arbitrarily large

Methodology Details

Problem Definition

Given a simple undirected graph $G$, find a pseudo 2-factor minimizing the number of non-cycle components. A pseudo 2-factor is a spanning subgraph of $G$ in which each connected component is isomorphic to $K_1$, $K_2$, or a cycle.

Main Technical Approach

1. Preliminary Results

• Observation 5: For every tree $T$ and each leaf $u$, $T$ has a maximum independent set containing $u$
• Proposition 6: Every tree $T$ has a pseudo 2-factor with exactly $α(T)$ components
• Proposition 7: Every forest $G$ has a pseudo 2-factor with exactly $α(G)$ components

2. Main Theorem Proof Strategy

The proof consists of two main steps:

Step 1: Construct a maximum 2-regular subgraph

• Select a union $F$ of vertex-disjoint cycles in $G$ such that $|V(F)|$ is maximized
• Subject to condition (a), minimize the number of isolated vertices in $G-V(F)$

Step 2: Handle the remaining forest

• Let $H = G - V(F)$ be a forest with $α = α(H)$
• By Proposition 7, $H$ has a pseudo 2-factor with exactly $α$ components
• The key is to prove $α ≤ f(G)$

3. Key Lemmas

Three key claims are proved by contradiction:

Claim 1: For a vertex $x$ in $H$, if $x$ has two neighbors $y_1, y_2$ in $V(F)$, then $y_1^+y_2^+ \notin E(G)$

Claim 2: For each isolated vertex $x$ in $H$, there exist two vertices $y, y'$ in $V(F)$ satisfying corresponding conditions

Claim 3: For each degree-1 vertex $x$ in $H$, there exists a neighbor satisfying the required conditions

Technical Innovations

1. Refined Analysis: Considers not only global independence number and minimum degree, but also local minimum degree for each independent set
2. Constructive Proof: Through explicit graph construction processes, demonstrates how to find pseudo 2-factors satisfying the conditions
3. Unified Framework: Incorporates several seemingly independent results into a unified theoretical framework

Experimental Setup

This is a pure theoretical paper without an experimental section. Results are verified primarily through mathematical proofs and constructive examples.

Constructive Examples

Example 1: Demonstrates tightness of the Bekkai-Kouider bound

• For any graph $H$ and positive integer $p ≥ |V(H)| + 1$
• Construct graph $G_1$ as the union of $H$ and $p$ disjoint copies of $K_2$
• Prove that every pseudo 2-factor of $G_1$ has at least $α(G_1) - δ(G_1) + 1$ non-cycle components

Example 2: Demonstrates advantages of the new bound

• Construct graph $G_2$ containing vertices $v_1, v_2$, independent sets $A_1, A_2$ (each with $k$ vertices), and complete graph $B$
• Calculate $α(G_2) - δ(G_2) + 1 = k + 1$, while $f(G_2) = 2$
• Show that the new bound is strictly superior to the original bound

Experimental Results

Main Theoretical Results

Theorem 4 (Main Result): Every graph $G$ has a pseudo 2-factor with at most $\max\{0, f(G)\}$ non-cycle components

Corollaries and Special Cases

1. When every independent set $I$ satisfies $δ_G(I) ≥ |I| + 1$, then $f(G) ≤ 0$, so $G$ has a 2-factor
2. For any graph $G$ and independent set $I$, we have $|I| - δ_G(I) + 1 ≤ α(G) - δ(G) + 1$, thus $f(G) ≤ α(G) - δ(G) + 1$
3. For forests, the bound in Theorem 4 is exact

Comparison of Bounds

Through Example $G_2$:

• Traditional bound: $α(G_2) - δ(G_2) + 1 = k + 1$
• New bound: $f(G_2) = 2$
• The improvement is significant, with the gap potentially arbitrarily large

Related Work

Historical Development

1. Tutte (1953): Provided necessary and sufficient conditions for graphs to have pseudo 2-factors without isolated vertices
2. Cornuéjols and Hartvigsen (1986): Extended results to cases without isolated vertices and small odd cycles
3. Enomoto and Li (2004): Studied pseudo 2-factor concepts (though not using this terminology)
4. Bekkai and Kouider (2009): Formally introduced the term "pseudo 2-factor" and proved Theorem 1
5. Niessen (1995): Proved degree conditions for 2-factor existence
6. Recent Work: Related research by Egawa and Furuya (2018), Chiba and Yoshida (recent)

Positioning of This Paper

Building on existing work, this paper:

• Provides more refined analytical tools
• Unifies several seemingly independent results
• Establishes tighter upper bounds

Conclusions and Discussion

Main Conclusions

1. Theoretical Contribution: Establishes a new upper bound $f(G)$ for the number of non-cycle components in pseudo 2-factors, which is tighter than previously known best results
2. Methodological Contribution: Introduces an analytical method considering local degrees of independent sets, providing new insights for related problems
3. Unification: Incorporates multiple related results into a unified framework, revealing their intrinsic connections

Limitations

1. Computational Complexity: Although the proof is constructive, computing $f(G)$ requires considering all independent sets, which may be computationally complex
2. Practical Applicability: As a pure theoretical result, practical applications are limited
3. Open Problems: Finding polynomial-time algorithms for computing pseudo 2-factors with minimum non-cycle components remains open

Future Directions

1. Algorithmic Research: Develop efficient algorithms for computing pseudo 2-factors with minimum non-cycle components
2. Generalizations: Consider more general graph classes or additional constraints
3. Applications: Explore applications in network design, matching theory, and related fields

In-Depth Evaluation

Strengths

1. Theoretical Depth: Sophisticated proof techniques, particularly the use of proof by contradiction and careful handling of graph construction details
2. Significance of Results: Not only improves known bounds but also unifies multiple related results, possessing important theoretical value
3. Completeness: Provides main results, proves tightness of bounds, and offers concrete improvement examples
4. Clarity of Presentation: Well-structured paper with detailed proof steps, easy to understand and verify

Weaknesses

1. Computational Complexity: No discussion of the complexity of computing $f(G)$, which is important for practical applications
2. Algorithmic Aspects: Although the proof is constructive, no explicit algorithm description is provided
3. Application Context: Lacks discussion of practical application scenarios

Impact

1. Academic Value: Provides new tools and perspectives for graph decomposition theory
2. Theoretical Contribution: Achieves substantial progress in 2-factor and pseudo 2-factor theory
3. Future Research: May inspire further research in graph decomposition and matching theory

Applicable Scenarios

1. Theoretical Research: Graph theory and combinatorial optimization research
2. Network Design: Potential applications in network connectivity and reliability analysis
3. Education: Suitable as teaching material for advanced graph theory courses

References

The paper cites 8 important references covering the main development of pseudo 2-factor theory:

1. Bekkai and Kouider (2009) - Pioneering work on pseudo 2-factors
2. Tutte (1953) - Classical results on graph factor decomposition
3. Niessen (1995) - Degree conditions for 2-factor existence
4. Enomoto and Li (2004) - Early related concepts
5. Other relevant recent developments

Overall Assessment: This is a high-quality theoretical paper achieving important progress in pseudo 2-factor theory of graphs. Although purely theoretical, its characteristic of unifying multiple known results and sophisticated proof techniques confer significant academic value.