Bicyclic graphs with the smallest and largest numbers of connected sets

Imagine a city made entirely of roads and intersections. In the world of mathematics, we call this a graph. The intersections are vertices (people or places), and the roads are edges (connections).

This paper is about a specific type of city: a Bicyclic Graph.

What is a "Bicyclic" City?

To understand this, let's start with the basics:

A Tree: Imagine a city with no loops. You can get from any house to any other house, but there is only one unique path to do so. If you leave your house, you can't come back to it without retracing your steps. This is a "Tree."
A Unicyclic Graph: Now, imagine you add just one extra road that creates a single loop (a roundabout). You can now drive around in a circle. This is a "Unicyclic" graph (one cycle).
A Bicyclic Graph: This is the star of our story. It's a city with two extra roads compared to a tree. This means the city has two loops. These loops might be separate, they might share a single intersection, or they might overlap like a figure-eight.

The Big Question: "Connected Sets"

The author, Audace Dossou-Olory, is asking a very specific question about these cities:

"How many different groups of people can form a 'connected club'?"

A Connected Set is a group of people (vertices) where everyone in the group can talk to everyone else without needing to step outside the group.

If you pick a random group of people, they might be scattered. Some might be on the other side of town with no road connecting them within the group. That's not a connected set.
If you pick a group where everyone is linked by roads that stay inside the group, that is a connected set.

The paper asks: For a city with $n$ people, what is the smallest and largest number of these "connected clubs" you can possibly have?

The Two Extremes: The "Boring" City vs. The "Party" City

The paper finds the two most extreme versions of these bicyclic cities.

1. The Smallest Number of Clubs (The "Lonely" City)

The Goal: To make it as hard as possible for people to form connected groups.
The Structure: Imagine two separate roundabouts (loops) far apart, connected by a very long, thin, straight road (a path).

Why it works: Because the city is stretched out, if you pick a group of people, it's very easy to accidentally pick someone who is "cut off" from the rest of the group. The long, thin path acts like a bottleneck. If you break the path, the group splits.
The Winner: The paper proves that the graph called $L_n$ (which looks like two small loops connected by a long stick) has the fewest possible connected sets. It's the most "fragmented" bicyclic city.

2. The Largest Number of Clubs (The "Super-Connected" City)

The Goal: To make it as easy as possible for people to form connected groups.
The Structure: Imagine a central hub (a busy intersection) where everything connects.

The Winner: The graph called $B_n$ .
The Analogy: Think of a massive party where one super-popular person (the center) knows everyone. Everyone else is just a "pendant" (a leaf) hanging off this one person. In this specific bicyclic city, the two loops are tiny (just triangles) and they both share the same central hub.
Why it wins: Because almost everyone is directly connected to the center, you can pick almost any random group of people, and they will likely still be connected through that central hub. It's the most "social" city possible.

The "Second Place" Party

The paper also finds the second-largest number of clubs. This is graph $R_n$ .

The Analogy: This is like the "Super-Connected" city, but instead of one person holding the whole party, there are two popular people who are best friends (connected by a road), and everyone else is attached to one of them. It's slightly less efficient at forming groups than the single-hub city, but still very social.

How Did They Figure This Out? (The Magic Tricks)

The author didn't just guess. They used "Graph Transformations," which are like magic tricks to rearrange the city without changing the number of people or roads.

The "Tree-Pruning" Trick: If a city has a long, thin branch (a tree) sticking out, the author showed that you can "move" that branch to a more central location to increase the number of connected groups.
The "Loop-Squashing" Trick: If you have two loops far apart, moving them closer together or merging them into a tighter shape changes the math.
The Logic: By repeatedly applying these tricks, they proved that:
1. To get the minimum, you must stretch the city out as much as possible (Type I structure).
2. To get the maximum, you must bunch everything together into a star shape (Type $B_n$ ).

Why Does This Matter?

You might ask, "Who cares about counting groups in a graph?"

Networks: This helps us understand how information spreads in social networks or computer networks. If a network is "stretched out" (like the minimum graph), a virus or a rumor might get stuck. If it's "bunched up" (like the maximum graph), everything spreads instantly.
Chemistry: Molecules are often graphs. Understanding how atoms (vertices) connect helps chemists predict how stable a molecule is.
Mathematics: It's a puzzle. Just like finding the shortest path between two cities, finding the "most" or "least" connected structures helps mathematicians understand the fundamental rules of how things can be connected.

Summary

The Problem: Count the number of "connected groups" in a city with two loops.
The Minimum: Found in a city where loops are far apart and connected by a long, thin road ( $L_n$ ). It's hard to form groups here.
The Maximum: Found in a city where everything is clustered around a single central hub ( $B_n$ ). It's easy to form groups here.
The Method: Using clever rearrangements to prove that no other shape can beat these two.

In short, the paper tells us that shape matters. Even if you have the same number of people and roads, how you arrange them determines whether your city is a collection of isolated islands or a bustling, connected metropolis.

1. Problem Statement

The paper investigates the extremal properties of connected sets in bicyclic graphs.

Definitions:
- A connected set in a graph $G=(V, E)$ is a nonempty subset $S \subseteq V$ that induces a connected subgraph.
- $N(G)$ denotes the total number of nonempty connected sets in $G$ .
- A bicyclic graph is a connected graph with $n$ vertices and $n+1$ edges. Such graphs contain exactly two or three cycles.
Objective: The author aims to determine the minimum and maximum values of $N(G)$ for the family $\mathcal{B}_n$ of all $n$ -vertex bicyclic graphs. Additionally, the paper seeks to characterize the specific graph structures that achieve these extreme values, as well as the structure achieving the second-largest value.

2. Methodology

The paper employs a combination of structural decomposition, graph transformations, and inductive arguments to solve the extremal problems.

Structural Decomposition (Lemma 3):
The author establishes that any bicyclic graph $G$ can be decomposed into a unique maximal induced bicyclic subgraph $G^*$ (containing no pendant vertices) with trees attached to the vertices of $G^*$ . The core structure $G^*$ falls into three types:
- Type I: Two disjoint cycles connected by a path ( $G[p, q, r]$ ).
- Type II: Two cycles sharing exactly one vertex (figure-eight shape).
- Type III: Two cycles sharing at least two vertices (theta graph structure).
Graph Transformations:
The primary technique involves modifying a graph to increase or decrease $N(G)$ while preserving the number of vertices ( $n$ ) and edges ( $n+1$ ).
- Pendant Vertex Removal/Attachment: Using Lemma 5, the author relates $N(G)$ to $N(G-v)$ and the number of connected sets containing the neighbor of a pendant vertex.
- Cycle Replacement: To minimize $N(G)$ , cycles are replaced with "tadpole" graphs (a cycle with a path attached). To maximize $N(G)$ , complex structures are transformed into configurations where a central vertex connects to all other vertices (star-like structures).
- Vertex Identification (Lemma 11): A crucial tool for maximization, this lemma compares graphs formed by identifying vertices in different ways. It proves that clustering connections to a single central vertex generally increases the number of connected sets.
Inductive Proofs:
The proofs for the minimum and maximum values rely heavily on induction on $n$ , utilizing known results for trees and unicyclic graphs (graphs with $n$ vertices and $n$ edges) as base cases or comparison points.

3. Key Contributions and Results

A. Minimum Number of Connected Sets

Extremal Graph: The graph $L_n$ $L_{n}$ (defined as $G[3, 3, n-4]$ $G [3, 3, n - 4]$ ) minimizes $N(G)$ $N (G)$ .
- Structure: Two triangles ( $C_3$ ) connected by a path of length $n-4$ .
Formula: For $n \ge 5$ :
$N(L_n) = \frac{(n+6)(n-1)}{2}$
Uniqueness: For $n > 5$ , $L_n$ is the unique graph achieving this minimum. For $n=5$ , both $L_5$ and another specific graph $A_5$ achieve the minimum (22).
Proof Strategy: The author proves that any graph not isomorphic to $L_n$ can be transformed into one with fewer connected sets by converting cycles into tadpole graphs or altering the cycle configuration to Type I.

B. Maximum Number of Connected Sets

Extremal Graph: The graph $B_n$ $B_{n}$ maximizes $N(G)$ $N (G)$ for $n \ge 8$ $n \geq 8$ .
- Structure: Constructed from a base graph $A_4$ (a 4-vertex bicyclic graph, essentially $K_4$ minus one edge) by attaching $n-4$ pendant edges to the unique vertex of degree 3 in $A_4$ .
Formula: For $n \ge 6$ :
$N(B_n) = n + 2 + 2^{n-1}$
Uniqueness: For $n > 7$ , $B_n$ is the unique maximizer.
Second-Largest Graph: The graph $R_n$ $R_{n}$ achieves the second-largest value.
- Structure: Constructed from two disjoint triangles ( $C_3$ ) sharing a vertex, with $n-5$ pendant edges attached to that shared vertex.
- Formula: $N(R_n) = n + 1 + 2^{n-1}$ .
- Note: $N(B_n) = N(R_n) + 1$ .

C. General Bounds and Lemmas

Lower Bound for Vertex-Containing Sets: For any $G \in \mathcal{B}_n$ and vertex $v$ , $N(G)_v \ge n+3$ .
Transformation Logic: The paper rigorously demonstrates that "spreading out" cycles (Type I) minimizes connectivity, while "concentrating" connections at a single high-degree vertex (Star-like attachment) maximizes connectivity.

4. Significance

Extension of Extremal Graph Theory: This work extends the well-studied field of extremal connected sets from trees and unicyclic graphs to bicyclic graphs, filling a gap in the literature regarding graphs with two cycles.
Structural Characterization: The paper provides a complete characterization of the extremal structures. It clarifies that the "most connected" bicyclic graphs are those that resemble a star graph with a small bicyclic core, while the "least connected" are those where cycles are separated by long paths.
Methodological Framework: The use of graph transformations (specifically replacing cycles with tadpoles or concentrating pendant edges) provides a robust framework that could be applied to other graph invariants or families of graphs with fixed cyclomatic numbers.
Applications: Understanding the number of connected sets is relevant to network reliability, chemical graph theory (counting substructures), and analyzing the robustness of complex networks.

Conclusion

The paper successfully resolves the extremal problems for the number of connected sets in bicyclic graphs. It identifies $L_n$ as the unique minimizer and $B_n$ as the unique maximizer (for $n \ge 8$ ), providing exact formulas for these values and proving that the second-largest value is achieved by $R_n$ . The results highlight a sharp contrast between the structural requirements for minimizing versus maximizing connectivity in graphs with a fixed number of cycles.