ABSTRACT Given a graph , the unlabeled subgraphs are called the cards of . The deck of is the multiset . Wendy Myrvold showed that a disconnected graph and a connected graph both on vertices have at most cards in common and found (infinite) families of trees and disconnected forests for which this upper bound is tight. Bowler, Brown, and Fenner conjectured that this bound is tight for . In this article, we prove this conjecture for sufficiently large . The main result is that a tree and a unicyclic graph on vertices have at most common cards. Combined with Myrvold's work, this shows that it can be determined whether a graph on vertices is a tree from any of its cards. On the basis of this theorem, it follows that any forest and nonforest also have at most common cards. Furthermore, the main ideas of the proof for trees are used to show that the girth of a graph on vertices can be determined based on any of its cards. Lastly, we show that any cards determine whether a graph is bipartite.
This paper makes significant advances in the field of graph reconstruction, specifically focusing on the problem of determining fundamental graph properties from an incomplete “deck” of vertex-deleted subgraphs. The core contribution lies in establishing concrete bounds on the number of common cards two structurally different graphs can share, enabling the recognition of trees, forests, girth, and bipartiteness with a limited set of observations.
The long-standing Reconstruction Conjecture, posed by Paul Kelly in 1942, posits that any graph with at least three vertices is uniquely determined by its deck (the multiset of all its vertex-deleted subgraphs). While this conjecture remains open, much research has focused on “partial reconstruction”—determining specific graph properties from the deck. This paper delves into an even more challenging variant: recognizing properties from an incomplete deck, meaning only a subset of the cards are available.
The significance of this work stems from its successful resolution of a key conjecture by Bowler, Brown, and Fenner (BBF) regarding the maximum number of common cards between a tree and a non-tree. Earlier work by Wendy Myrvold (1989, 1990) showed that a non-connected graph and a connected graph on n
vertices can have at most ⌊n/2⌋ + 1
common cards, and that trees can be reconstructed from just three specific cards. Myrvold also found infinite families of trees and non-connected forests that achieve this ⌊n/2⌋ + 1
common card bound. The BBF conjecture (2010) specifically predicted this bound was tight for trees versus connected non-trees when n ≥ 44
.
The key innovation of this paper is the rigorous proof that for sufficiently large n
(specifically, n ≥ 5000
), a tree and a unicyclic graph (a connected graph with exactly one cycle) on n
vertices can have at most ⌊n/2⌋ + 1
common cards. This effectively proves the BBF conjecture for large n
. The consequence is a definitive result: it can be determined whether a given graph on n
vertices is a tree from any ⌊n/2⌋ + 2
of its cards.
The methodology employed to achieve this involves several innovative techniques:
1. Focus on the “Hard Case”: The paper first establishes that if a non-tree graph has more than one cycle, it shares very few common cards with a tree (at most two). This allows the analysis to concentrate on the challenging scenario where the non-tree graph is unicyclic. The “hidden” cycle within the unicyclic graph becomes the central distinguishing feature.
2. Sophisticated Coloring Arguments: A primary innovation is the development and application of intricate “coloring” schemes. Vertices in the unicyclic graph are colored (e.g., “red” or “white”) based on their structural properties, particularly their proximity to “large” branches or critical cycle components. This allows the authors to strategically identify which vertices, if removed, would result in a card that could be isomorphic to a tree card. By demonstrating that “bad” vertices (whose removal might create ambiguity) cannot correspond to common cards, they systematically narrow down the possibilities.
3. Detailed Combinatorial Bounding: The proof relies on a series of rigorous counting arguments and bounds on graph parameters. This includes bounding the length of the cycle in the unicyclic graph, the heights of branches attached to the cycle, and the number of leaves. These precise bounds are crucial for showing that, beyond a certain number of common cards, the structural differences between a tree and a unicyclic graph become undeniable.
4. Generalizability: The paper demonstrates the power of its coloring-based approach by extending it beyond tree recognition. Similar techniques are successfully applied to determine if a graph is a forest (from ⌊n/2⌋ + 2
cards), its girth (from ⌊2n/3⌋ + 1
cards), and whether it is bipartite (from ⌊5n/6⌋ + 2
cards). This showcases a versatile new framework for partial graph reconstruction.
The main prior ingredients upon which this research builds include:
* Paul Kelly’s Reconstruction Conjecture (1942): Provides the foundational problem and context for the entire field.
* Wendy Myrvold’s work (1980s-1990s): Her pioneering results on the ally-reconstruction number, especially for trees and connected/disconnected graphs, laid the groundwork for understanding how many cards are needed to determine certain properties. The ⌊n/2⌋ + 1
common card bound is directly inherited from her research.
* Bowler, Brown, and Fenner’s Conjectures (2010): These conjectures, specifically regarding the tightness of the ⌊n/2⌋ + 1
bound for trees versus connected non-trees, are the direct motivation and target of the main theorem. Their identification of specific “adversary” graph pairs (like caterpillar trees and sunshine graphs) provides concrete examples that test the limits of reconstructibility.
* Fundamental Graph Theory Concepts: Standard definitions and properties of graphs, trees, forests, cycles, degrees, paths, and components are indispensable tools used throughout the paper’s intricate combinatorial arguments.
* Counting and Extremal Combinatorics: The paper heavily relies on established techniques from counting and extremal combinatorics to derive its various bounds and prove its lemmas by contradiction.
In summary, this paper provides a significant breakthrough in graph reconstruction by confirming a major conjecture for large graphs, demonstrating that distinguishing trees from unicyclic graphs (the most challenging case) can be done with a remarkably high proportion of missing information. Its novel coloring and combinatorial bounding techniques offer a powerful general framework for tackling similar recognition problems for other fundamental graph properties.