Lollipops, Dense Cycles and Chords

Basic Information

• Paper ID: 2502.04726
• Title: Lollipops, dense cycles and chords
• Authors: Zdeněk Dvořák, Beatriz Martins, Stéphan Thomassé, Nicolas Trotignon
• Classification: math.CO (Combinatorics)
• Publication Date: October 13, 2025
• Paper Link: https://arxiv.org/abs/2502.04726

Abstract

In 1980, Gupta, Kahn, and Robertson proved that every graph $G$ with minimum degree at least $k \geq 2$ contains a cycle $C$ with at least $k+1$ vertices, each having at least $k$ neighbors in $C$ (thus $C$ has at least $\frac{(k+1)(k-2)}{2}$ chords). This paper further demonstrates that graphs with high minimum degree can be obtained by contracting certain edges (called cycle minors). Subsequently, cycles with cliques as cycle minors are studied, and it is proven that minimum degree at least $O(k^2)$ guarantees the existence of a cycle $K_k$-minor.

Research Background and Motivation

Problem Background

1. Continuation of Classical Problems: A classical problem in graph theory is studying the relationship between minimum degree and dense substructures in graphs. Many theorems show that sufficiently high minimum degree in a graph guarantees the existence of some dense, complex, or well-connected substructure.
2. Limitations of Existing Results: Although the Gupta-Kahn-Robertson theorem guarantees the existence of cycles with many chords, it does not further investigate the structural properties of these cycles, particularly what dense structures can be obtained through edge contraction operations.
3. Application of the Lollipop Method: Since Thomason first introduced the lollipop method in 1978, it has been primarily used to prove the existence of Hamiltonian cycles. This paper extends its application to constructing dense contracted cycles.

Research Motivation

The core motivation of this paper is to extend the classical GKR theorem from simple chord counting to structural analysis. By introducing the concept of "cycle minors," the paper investigates how to obtain denser graph structures from dense cycles through edge contraction operations.

Core Contributions

1. Extension of GKR Theorem: Not only proves the existence of dense cycles but also demonstrates that graphs with high minimum degree or high average degree can be obtained through contraction operations.
2. Introduction of Cycle Minor Concept: Defines the concept of cycle minors, namely graphs obtained from a Hamiltonian subgraph of a graph by contracting certain edges of a Hamiltonian cycle.
3. Establishment of Relationship Between Degree and Cycle Minors: Proves that $f(\ell) = O(\ell^2)$, where $f(\ell)$ is the lower bound on minimum degree guaranteeing the existence of $K_\ell$ as a cycle minor.
4. Provision of Algorithmic Framework: Provides polynomial-time algorithms to construct cycles satisfying the theorem conditions and corresponding edge contraction sets.

Detailed Methodology

Task Definition

Given a graph $G$ with minimum degree $k$, construct a cycle $C$ and its edge subsets $X_1, X_2$ such that contracting edges in $X_i$ yields graphs with high minimum degree or high average degree.

Core Concepts

Lollipop Structure

Definition: A lollipop $L$ in graph $G$ is a pair $(P,C)$ where:

• $P = p_1...p_s$ is a path
• $C = c_1...c_tc_1$ is a cycle
• $p_s = c_1$ and $V(P) \cap V(C) = \{c_1\}$

Optimality: A lollipop $L = (P,C)$ is optimal if and only if:

• $L$ is maximal in the vertex inclusion sense
• Among all lollipops defined on $V(L)$, $L$ has maximum cycle length

Active Path System

Construct active path sets $S_1, S_2, ...$ through recursive definition:

• $S_1 = \{c_1c_2...c_t, c_1c_tc_{t-1}...c_2\}$
• For $i \geq 1$, construct $S_{i+1}$ from $S_i$: for $Q = c_1...u \in S_i$ and chord $uv$, if $vw$ is an edge of $C$ ($w$ is the neighbor of $v$ in $vQu$), then add path $c_1QvuQw$ to $S_{i+1}$

Main Theorems

Theorem 1.1 (Main Result)

If $G$ has minimum degree at least $k \geq 2$, then $G$ contains a cycle $C$ satisfying:

1. $C$ contains at least $k+1$ vertices, each having at least $k$ neighbors in $C$
2. There exist $X_1, X_2 \subseteq E(C)$ such that:
   • Contracting edges in $X_1$ yields a graph with minimum degree at least $\lceil\frac{k+2}{2}\rceil$
   • Contracting edges in $X_2$ yields a graph with average degree at least $\frac{2}{3}(k+1)$

Technical Innovations

1. Refined Analysis: Not only counts the number of chords but analyzes their distribution patterns, ensuring sufficient "crossing chords" to support effective edge contraction.
2. Active Vertex Theory: Systematically identifies vertices with high degree through the concept of active paths and analyzes their behavior in contraction operations.
3. Application of Marcus-Tardos Theorem: Utilizes this theorem to further contract cycle minors with high average degree into large complete bipartite graphs.

Experimental Setup

Theoretical Verification

This paper is primarily theoretical work, verifying results through rigorous mathematical proofs:

1. Small-Scale Verification:
   • $f(3) = 2$, $f(4) = 3$, $6 \leq f(5) \leq 8$
   • Verifies the existence of cycle minors for small cliques through explicit constructions
2. Extremal Examples:
   • Complete graph $K_t$ as a tight example, showing that certain conclusions are optimal
   • Icosahedron showing $f(5) \geq 6$

Algorithm Complexity Analysis

Provides polynomial-time algorithms:

• DFS for finding initial lollipop: $O(n+m)$
• Iterations for improving lollipop: at most $n^2$ calls
• Overall complexity: polynomial time

Experimental Results

Main Results

Existence of Cycle Minors

• Theorem 3.2: For each integer $\ell$, there exists an integer $k$ such that graphs with minimum degree at least $k$ contain $K'_{\ell,\ell}$ as a cycle minor
• Lemma 3.4: $f(k) = O(k^2)$, meaning $O(k^2)$ minimum degree is required for the existence of $K_k$ cycle minor

Specific Numerical Results

• $f(3) = 2$: Minimum degree 2 guarantees $K_3$ cycle minor
• $f(4) = 3$: Minimum degree 3 guarantees $K_4$ cycle minor
• $f(5) \leq 8$: Minimum degree 8 guarantees $K_5$ cycle minor

Constructive Proofs

Provides explicit constructions via the lollipop method:

1. Find optimal lollipop $(P,C)$
2. Identify active vertices (at least $k$)
3. Construct contraction edge sets $X_1, X_2$
4. Verify degree properties of contracted graphs

Algorithm Validity

Proves correctness and polynomial-time complexity of the algorithm:

• Each iteration either finds a better lollipop or obtains the desired cycle
• Requires at most $n^2$ iterations
• Each iteration completes in polynomial time

Related Work

Classical Results

1. GKR Theorem (1980): Direct foundation of this paper, proving the existence of dense cycles
2. Lollipop Method: First introduced by Thomason (1978), primarily used for Hamiltonian cycle problems
3. Marcus-Tardos Theorem: Used for matrix blocking, applied in this paper to graph contraction

Related Directions

1. Graph Minor Theory: Results by Kostochka and de la Vega on standard minors
2. Connectivity Theory: Related work on k-linked graphs
3. Chromatic Number and Chords: Recent research on chromatic numbers of graphs with restricted chords

Position of This Paper

Building on classical degree-density theorems, this paper introduces the perspective of edge contraction and opens new research directions.

Conclusions and Discussion

Main Conclusions

1. High minimum degree not only guarantees the existence of dense cycles but also ensures that denser structures can be obtained through contraction
2. The concept of cycle minors provides new tools for studying graph structures
3. The degree bound of $O(k^2)$ is a sufficient condition for obtaining $K_k$ cycle minors

Limitations

1. Optimality of Quadratic Bound: It remains unclear whether $f(k) = O(k^2)$ is optimal; the authors conjecture that a bound of $O(k\sqrt{\log k})$ may exist
2. Algorithm Complexity: Although polynomial-time, the $O(n^2)$ iteration count may be slow in practical applications
3. Structural Restrictions: Certain structures (such as bipartite configurations) limit possible cycle minors

Future Directions

1. Question 1.2: Is $f(\ell) = O(\ell\sqrt{\log \ell})$?
2. Questions 4.1-4.2: Simple criteria for determining active paths
3. Questions 4.3-4.4: Linear bounds on the number of cycle chords in graphs with minimum degree 3

In-Depth Evaluation

Strengths

1. Theoretical Depth: Extends classical results to new heights, introducing valuable new concepts
2. Technical Innovation: Refined application of the lollipop method, establishment of active path theory
3. Completeness: From existence proofs to algorithm implementation, from small-scale verification to asymptotic analysis
4. Clear Writing: Concepts are well-defined, proof structure is logical

Weaknesses

1. Limited Practical Applicability: Primarily theoretical results with unclear practical application scenarios
2. Technical Complexity: Proof techniques are quite complex, potentially limiting the generalizability of results
3. Many Open Problems: Multiple unresolved questions suggest the theory is not yet complete

Impact

1. Academic Value: Provides new perspectives for studying the relationship between degree and structure in graph theory
2. Methodological Contribution: The cycle minor concept may have applications in other problems
3. Foundation for Future Research: Establishes the foundation for research on related problems

Applicable Scenarios

1. Theoretical Graph Theory Research: Provides tools for studying dense substructures in graphs
2. Algorithm Design: May have applications in algorithms requiring dense subgraph discovery
3. Network Analysis: May be useful in analyzing local density in large-scale networks

References

This paper cites 18 important references, including:

• GKR80 Original work by Gupta, Kahn, Robertson
• MT04 Marcus-Tardos theorem
• Tho78 Thomason's pioneering work on the lollipop method
• TW05 Thomas-Wollan results on k-linked graphs

Summary: This is a high-quality theoretical graph theory paper that achieves substantial progress based on classical results. Although primarily theoretical, the concepts and methods it introduces provide valuable tools for development in related fields. The paper demonstrates high technical level, rigorous proofs, and represents an important contribution to combinatorial mathematics.