On the minimum degree of minimal $k$-$\{1,2\}$-factor critical $k$-planar graphs

This paper proves that the conjecture stating every minimal $k$-$\{1,2\}$-factor critical graph $G$ satisfies $k+1 \le \delta(G) \le k+2$ holds true for the class of $k$-planar graphs, thereby resolving the conjecture specifically for planar graphs.

The Gist

Imagine you have a large, complex social network of friends. In the world of mathematics, this network is called a graph, where people are vertices (dots) and friendships are edges (lines connecting the dots).

This paper is about a specific type of "social resilience" in these networks. Let's break down the big ideas using simple analogies.

1. The "Perfect Party" Concept ({1, 2}-factors)

Imagine you want to organize a party for everyone in your network. You have two rules for how people can pair up:

• Rule A: Everyone must have exactly one partner (like a dance). This is a Perfect Matching.
• Rule B: Everyone must be in a group of either 2 people (a pair) or 3 people (a small circle). No one is left alone, and no one is in a group of 4 or more.

In math, a group of people following Rule B is called a {1, 2}-factor. It's a way of saying, "Everyone is connected to at least one other person, but no one is overwhelmed by too many connections."

2. The "Resilience" Test (k-Factor-Critical)

Now, imagine your network is k-factor-critical. This means the network is super tough.

• If you kick out any $k$ people from the party (maybe they got sick or left town), the remaining people can still form perfect pairs or small circles.
• The network is so well-connected that losing a few members doesn't break the party.

3. The "Minimal" Condition

The paper focuses on minimal networks. Think of this as a "barely holding it together" situation.

• A network is minimal if it is resilient, but if you remove just one single friendship (edge), the whole system collapses.
• It's like a house of cards: it stands perfectly, but if you pull out just one card, the structure fails.

4. The Big Question: How Many Friends Do You Need?

The mathematicians wanted to know: What is the minimum number of friends (connections) a person in this "minimal" network must have?

• The Old Guess: For the simpler "Perfect Matching" rule, experts guessed that everyone needs at least $k+1$ friends.
• The New Guess: For the more complex "{1, 2}-factor" rule (pairs and trios), experts guessed that everyone needs between $k+1$ and $k+2$ friends. They thought it was impossible for someone to need $k+3$ friends in these minimal networks.

5. The "Planar" Twist

The paper specifically looks at Planar Graphs.

• Analogy: Imagine drawing your social network on a piece of paper. If you can draw all the friendships without any lines crossing each other (except at the people's dots), it's a planar graph.
• The "k-Planar" Twist: The authors looked at even tougher networks. A k-planar graph is one where, even if you remove any $k$ people, the remaining network can still be drawn on paper without crossing lines.
  • Example: A standard map is planar. If you remove a few countries and the rest of the map can still be drawn without borders crossing, it's "k-planar."

6. The Main Discovery

The author, Kevin Pereyra, proved the new guess is correct for these planar networks.

The Result:
If you have a minimal network that is tough enough to survive losing $k$ people, and the network is "planar" (drawable without crossing lines), then every single person in that network has either $k+1$ or $k+2$ friends.

They proved that no one needs $k+3$ friends (or more) to keep the network minimal and resilient.

Why Does This Matter?

Think of it like designing a power grid or a road system:

• You want the system to be efficient (minimal connections).
• You want it to be resilient (if $k$ roads close, traffic still flows).
• You want to know the "worst-case scenario" for a single intersection: How many roads must connect to it to keep the system working?

This paper tells city planners (or network engineers) that for certain types of flat, non-crossing networks, the "traffic load" on any single intersection is strictly limited. It can't get too heavy; it's capped at just one or two connections more than the number of failures you are preparing for.

Summary in One Sentence

The paper proves that in any "barely resilient" network that can be drawn on a flat map without crossing lines, every person is connected to either $k+1$ or $k+2$ others, never more.

Technical Summary

Here is a detailed technical summary of the paper "On the minimum degree of minimal k-{1, 2}-factor critical k-planar graphs" by Kevin Pereyra.

1. Problem Statement and Context

The paper addresses a conjecture regarding the minimum degree ($\delta(G)$) of minimal $k$-{$1, 2$}-factor critical graphs.

• Definitions:
  • A $\{1, 2\}$-factor is a spanning subgraph where every component is a regular graph of degree 1 or 2 (essentially a collection of disjoint cycles and edges).
  • A graph $G$ is **$k$-{$1, 2}-factor critical** if the removal of any set of k$vertices results in a graph containing a${1, 2}$-factor.
  • A graph is minimal $k$-{$1, 2}-factor critical if it possesses the property, but the removal of any single edge e$ destroys it.
• The Conjecture:
  Previous research established that for any $k$-{$1, 2}-factor critical graph, \delta(G) \geq k+1$. However, unlike standard$k$-factor-critical graphs (where the minimum degree is conjectured to be exactly$k+1$), minimal$k-{1, 2}-factor critical graphs can have a minimum degree of k+2$.
  Conjecture 1.7 posits that for any minimal $k$-{$1, 2}-factor critical graph G$:
  $$k + 1 \leq \delta(G) \leq k + 2$$
• The Gap: While the conjecture was proven for specific values of $k$ (e.g., $k \in \{0, 1, n-5, \dots\}$) and for claw-free graphs, it remained open for general planar and $k$-planar graphs.
• Objective: The paper aims to prove Conjecture 1.7 specifically for $k$-planar graphs (graphs where the deletion of any $k$ vertices yields a planar graph). This includes standard planar graphs as a special case ($k=0$).

2. Methodology

The authors employ a combination of structural graph theory, extremal graph theory, and properties of planar graphs. The methodology proceeds as follows:

1. Characterization via Independent Sets:
   The proof relies on the characterization of $k$-{$1, 2}-factor critical graphs using independent sets and neighborhood sizes (derived from Theorem 1.4 and Lemma 3.2). Specifically, if a graph G$is minimal, there exists a set$S$such that removing an edge$e$creates a violation of the${1, 2}$-factor condition. This implies the existence of an independent set$S$where the neighborhood size drops significantly upon the removal of$e$.

2. Reduction to Planar Bipartite Graphs:
   The core strategy involves analyzing the subgraph induced by the critical independent set $S$ and its neighborhood $N(S)$. By removing edges within the neighborhood $N(S)$, the authors construct a bipartite planar graph (or a graph that becomes planar after edge removal).

   • They utilize Euler's Formula ($n - m + f = 2$) and the property that faces in bipartite planar graphs have length at least 4 to derive upper bounds on the number of edges ($m \leq 2n - 4$).

3. Degree Analysis via Contradiction:
   The authors assume the contrary: that every vertex in the critical set $S$ has a degree $\geq 4$ (or higher, depending on $k$).

   • They sum the degrees of vertices in $S$ and compare this sum to the maximum possible number of edges in the constructed planar bipartite graph.
   • This leads to a contradiction (e.g., $2n \leq m \leq 2n-4$), proving that there must exist at least one vertex in$S$ with a low degree.

4. Case Analysis:
   The proof is divided based on the value of $k$:

   • Case $k=0$: Analyzes planar graphs directly.
   • Case $k>0$: Reduces the problem to a 1-{1, 2}-factor critical subgraph $G'$ obtained by removing $k-1$ vertices. The planarity of $G'$ is guaranteed by the definition of $k$-planar graphs.

3. Key Contributions

• Proof of Conjecture for $k$-Planar Graphs: The paper provides a rigorous proof that Conjecture 1.7 holds for all $k$-planar graphs.
• Refined Bounds:
  • For $k=0$ (standard planar graphs), the authors prove $k+1 \leq \delta(G) \leq k+3$ (i.e., $1 \leq \delta(G) \leq 3$).
  • For $k>0$ ($k$-planar graphs), the authors prove the tight bound: $k+1 \leq \delta(G) \leq k+2$.
• Structural Lemmas: The paper establishes several new lemmas (3.5–3.8) regarding the minimum degree of vertices in specific types of planar bipartite graphs with unbalanced partitions (e.g., $|A| \approx |B|$ or $|A| = |B| \pm 1$). These lemmas are instrumental in the main proof and may have independent utility in graph theory.
• Tightness of Bounds: The authors provide explicit examples (including $K_4$, $K_5$, and specific constructed graphs) demonstrating that the bounds $k+1$ and $k+2$ are attainable, confirming the tightness of the results.

4. Main Results

Theorem 3.9:
Let $G$ be a $k$-{$1, 2}-factor-critical graph such that G-e$is not$k-{1, 2}-factor-critical for some edge e$.

• If $k=0$ and $G$ is planar, then $1 \leq \delta(G) \leq 3$.
• If $k>0$ and $G$ is $k$-planar, then $k+1 \leq \delta(G) \leq k+2$.

Theorem 3.14:
Let $G$ be a minimal $k$-{$1, 2$}-factor-critical planar graph. Then:
$$k + 1 \leq \delta(G) \leq k + 2$$

Theorem 3.13:
Let $G$ be a minimal $k$-{$1, 2}-factor-critical graph such that for every set S$of size$k-1$,$G-S$is planar. Then$k+1 \leq \delta(G) \leq k+2$.

5. Significance

• Resolution of a Long-standing Conjecture: The paper resolves Conjecture 1.7 for the broad and important class of planar and $k$-planar graphs, a significant step in the structural theory of factor-critical graphs.
• Distinction from $k$-Factor-Criticality: The results highlight a fundamental difference between standard $k$-factor-critical graphs (where $\delta(G)=k+1$ is conjectured) and $k$-{$1, 2}-factor-critical graphs (where \delta(G)$can reach$k+2$). The paper clarifies exactly when this higher degree occurs in planar settings.
• Methodological Advancement: The technique of reducing the problem to the analysis of induced bipartite subgraphs and applying Euler's formula constraints offers a powerful tool for analyzing minimum degrees in sparse graph classes.
• Future Directions: The paper concludes with Conjecture 3.15, suggesting that if a graph is minimal for both $t=k$ and $t=k+1$, it must be a complete graph. This opens a new avenue for research into the structural rigidity of these graphs.

In summary, this paper successfully extends the understanding of minimal factor-critical graphs to the realm of planar and $k$-planar graphs, providing tight bounds on their minimum degrees and establishing the validity of the relevant conjecture in these contexts.