Recognizing Trees From Incomplete Decks

Abstract

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.

Locations

  • Journal of Graph Theory
  • arXiv (Cornell University)

Ask a Question About This Paper

Summary

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.

For a given graph, the unlabeled subgraphs $G-v$ are called the cards of $G$ and the deck of $G$ is the multiset $\{G-v: v \in V(G)\}$. Wendy Myrvold [Ars Combinatoria, … For a given graph, the unlabeled subgraphs $G-v$ are called the cards of $G$ and the deck of $G$ is the multiset $\{G-v: v \in V(G)\}$. Wendy Myrvold [Ars Combinatoria, 1989] showed that a non-connected graph and a connected graph both on $n$ vertices have at most $\lfloor \frac{n}{2} \rfloor +1$ cards in common and she found (infinite) families of trees and non-connected forests for which this upper bound is tight. Bowler, Brown, and Fenner [Journal of Graph Theory, 2010] conjectured that this bound is tight for $n \geq 44$. In this article, we prove this conjecture for sufficiently large $n$. The main result is that a tree $T$ and a unicyclic graph $G$ on $n$ vertices have at most $\lfloor \frac{n}{2} \rfloor+1$ common cards. Combined with Myrvold's work this shows that it can be determined whether a graph on $n$ vertices is a tree from any $\lfloor \frac{n}{2}\rfloor+2$ of its cards. Based on this theorem, it follows that any forest and non-forest also have at most $\lfloor \frac{n}{2} \rfloor +1$ common cards. Moreover, we have classified all except finitely many pairs for which this bound is strict. Furthermore, the main ideas of the proof for trees are used to show that the girth of a graph on $n$ vertices can be determined based on any $\frac{2n}{3} +1$ of its cards. Lastly, we show that any $\frac{5n}{6} +2$ cards determine whether a graph is bipartite.
The $\ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $\ell$ vertices. In 1976, Giles proved that any tree on $n\geq 6$ vertices can … The $\ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $\ell$ vertices. In 1976, Giles proved that any tree on $n\geq 6$ vertices can be reconstructed from its $\ell$-deck for $\ell \geq n-2$. Our main theorem states that it is enough to have $\ell\geq (8/9+o(1))n$, making substantial progress towards a conjecture of N\'ydl from 1990. In addition, we can recognise connectedness from the $\ell$-deck if $\ell\geq 9n/10$, and reconstruct the degree sequence from the $\ell$-deck if $\ell\ge \sqrt{2n\log(2n)}$. All of these results are significant improvements on previous bounds.
Abstract The deck of a graph is given by the multiset of (unlabeled) subgraphs . The subgraphs are referred to as the cards of . Brown and Fenner recently showed … Abstract The deck of a graph is given by the multiset of (unlabeled) subgraphs . The subgraphs are referred to as the cards of . Brown and Fenner recently showed that, for , the number of edges of a graph can be computed from any deck missing 2 cards. We show that, for sufficiently large , the number of edges can be computed from any deck missing at most cards.
The $\ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $\ell$ vertices. We say that a graph is reconstructible from its $\ell$-deck if no … The $\ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $\ell$ vertices. We say that a graph is reconstructible from its $\ell$-deck if no other graph has the same $\ell$-deck. In 1957, Kelly showed that every tree with $n\ge3$ vertices can be reconstructed from its $(n-1)$-deck, and Giles strengthened this in 1976, proving that trees on at least 6 vertices can be reconstructed from their $(n-2)$-decks. Our main theorem states that trees are reconstructible from their $(n-r)$-decks for all $r\le n/{9}+o(n)$, making substantial progress towards a conjecture of N\'ydl from 1990. In addition, we can recognise the connectedness of a graph from its $\ell$-deck when $\ell\ge 9n/10$, and reconstruct the degree sequence when $\ell\ge\sqrt{2n\log(2n)}$. All of these results are significant improvements on previous bounds.
A graph is reconstructible if it is determined up to isomorphism from the collection of all its one-vertex deleted unlabeled subgraphs. One of the foremost unsolved problems in Graph Theory … A graph is reconstructible if it is determined up to isomorphism from the collection of all its one-vertex deleted unlabeled subgraphs. One of the foremost unsolved problems in Graph Theory is the Reconstruction Conjecture, which asserts that every graph G on at least three vertices is reconstructible. In 1980’s, tremendous work was done and many significant results have been produced on the problem and its variations. During the last three decades, work on it has slowed down gradually. P. J. Kelly (1957) first noted that trees are reconstructible; but the proof is quite lengthy. A short proof, due to Greenwell and Hemminger (1973), was given which is based on a simple, but powerful, counting theorem. This chapter deals with the counting theorem and its subsequent applications; also it ends up with a reduction of the Reconstruction Conjecture using distance and connectedness, which may lead to the final solution of the conjecture.
Abstract The vertex‐deleted subgraph G − v , obtained from the graph G by deleting the vertex v and all edges incident to v , is called a card of … Abstract The vertex‐deleted subgraph G − v , obtained from the graph G by deleting the vertex v and all edges incident to v , is called a card of G . The deck of G is the multiset of its unlabelled vertex‐deleted subgraphs. The number of common cards of G and H (or between G and H ) is the cardinality of the multiset intersection of the decks of G and H . In this article, we present infinite families of pairs of graphs of order n ≥ 4 that have at least \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}2\lfloor\frac{1}{3}(n-1)\rfloor\end{eqnarray*}\end{document} common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n . This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\frac{2}{3}(n+5-2\sqrt{3n+6})\end{eqnarray*}\end{document} common cards, for appropriate values of n , from which we can construct pairs having slightly fewer common cards for all other values of n ≥10. We also present infinite families of pairs of forests and pairs of trees with \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}2\lfloor\frac{1}{3}(n-4)\rfloor\end{eqnarray*}\end{document} and \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}2\lfloor\frac{1}{3}(n-5)\rfloor\end{eqnarray*}\end{document} common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 146–163, 2010
The deck of a graph $G$ is given by the multiset of (unlabelled) subgraphs $\{G-v:v\in V(G)\}$. The subgraphs $G-v$ are referred to as the cards of $G$. Brown and Fenner … The deck of a graph $G$ is given by the multiset of (unlabelled) subgraphs $\{G-v:v\in V(G)\}$. The subgraphs $G-v$ are referred to as the cards of $G$. Brown and Fenner recently showed that, for $n\geq29$, the number of edges of a graph $G$ can be computed from any deck missing 2 cards. We show that, for sufficiently large $n$, the number of edges can be computed from any deck missing at most $\frac1{20}\sqrt{n}$ cards.
The deck of a graph $G$ is given by the multiset of (unlabelled) subgraphs $\{G-v:v\in V(G)\}$. The subgraphs $G-v$ are referred to as the cards of $G$. Brown and Fenner … The deck of a graph $G$ is given by the multiset of (unlabelled) subgraphs $\{G-v:v\in V(G)\}$. The subgraphs $G-v$ are referred to as the cards of $G$. Brown and Fenner recently showed that, for $n\geq29$, the number of edges of a graph $G$ can be computed from any deck missing 2 cards. We show that, for sufficiently large $n$, the number of edges can be computed from any deck missing at most $\frac1{20}\sqrt{n}$ cards.
An edge-card of a graph G is a subgraph formed by deleting an edge. The edge-reconstruction number of a graph G, ern(G), is the minimum number of edge-cards required to … An edge-card of a graph G is a subgraph formed by deleting an edge. The edge-reconstruction number of a graph G, ern(G), is the minimum number of edge-cards required to determine G up to isomorphism. A da-ecard is an edge-card which also specifies the degree of the deleted edge, that is, the number of edges adjacent to it. The degree-associated edge-reconstruction number, dern(G) is the minimum number of da- ecards that suffice to determine the graph G. In this paper we state some known results on the edge-reconstruction number of disconnected graphs and trees. Then we investigate how the degree-associated edge- reconstruction number of disconnected graphs and trees vary from their respective edge-reconstruction number. We show how we can select two da-ecards to identify caterpillars uniquely. Finally we conjecture that for any tree T, dern(T)<= 2.
This chapter considers the richness of mathematics and mathematicians' responses to it, with a particular focus on various types of graphs. It begins with a discussion of theorems from many … This chapter considers the richness of mathematics and mathematicians' responses to it, with a particular focus on various types of graphs. It begins with a discussion of theorems from many areas of mathematics that have been judged among the most beautiful, including the Euler Polyhedron Formula; the number of primes is infinite; there are five regular polyhedra; there is no rational number whose square is 2; and the Four Color Theorem. The chapter proceeds by describing regular graphs, irregular graphs, irregular multigraphs and weighted graphs, subgraphs, and isomorphic graphs. It also analyzes the degrees of the vertices of a graph, along with concepts and ideas concerning the structure of graphs. Finally, it revisits a rather mysterious problem in graph theory, introduced by Stanislaw Ulam and Paul J. Kelly, that no one has been able to solve: the Reconstruction Problem.
A graph G is an NG-graph if \chi(G) + \chi(G complement) = |V(G)| + 1. We characterize NG-graphs solely from degree sequences leading to a linear-time recognition algorithm. We also … A graph G is an NG-graph if \chi(G) + \chi(G complement) = |V(G)| + 1. We characterize NG-graphs solely from degree sequences leading to a linear-time recognition algorithm. We also explore the connections between NG-graphs and split graphs. There are three types of NG-graphs and split graphs can also be divided naturally into two categories, balanced and unbalanced. We characterize each of these five classes by degree sequence. We construct bijections between classes of NG-graphs and balanced and unbalanced split graphs which, together with the known formula for the number of split graphs on n vertices, allows us to compute the sizes of each of these classes. Finally, we provide a bijection between unbalanced split graphs on n vertices and split graphs on n-1 or fewer vertices providing evidence for our conjecture that the rapid growth in the number of split graphs comes from the balanced split graphs.
On the Maximum Number of Common Cards between Various Classes of Graphs The Reconstruction Conjecture is one of the foremost unsolved problems in graph theory. It conjectures that a graph … On the Maximum Number of Common Cards between Various Classes of Graphs The Reconstruction Conjecture is one of the foremost unsolved problems in graph theory. It conjectures that a graph can be uniquely determined, up to isomorphism, by its collection of unlabelled vertex-deleted subgraphs (called its deck of cards). Like many mathematical problems, its appeal lies in the simplicity of its hypothesis and its accessibility to non-experts. However, although many graph theorists have tried to resolve the status of conjecture, it is still an open problem. Since the conjecture has remained unresolved, attention has focused on related reconstruction problems. One such area is the study of the two reconstruction numbers of some particular graph G: the existential reconstruction number rn(G), defined to be the minimum k such that there exists k cards from which G can be reconstructed, and the universal reconstruction number urn(G), defined to be the minimum k such that G can be reconstructed from any k cards. Most work on reconstruction numbers yet published concerns rn(G). This thesis instead focusses on urn(G) and will be one of the first to contain substantial results on this topic. urn(G) can also be studied in terms of the maximum number of common cards that G can have with any other graph, and that is the approach that we take. We find upper bounds for the maximum number of common cards between pairs of graphs in various classes and, in all cases, we show that these bounds can be attained by infinite families. Moreover, we completely characterise the families of pairs of graphs that attain the bounds. In doing so, we present many families of graph pairs with different values on various parameters that have, by far, the largest number of common cards yet published.
The vertex-deleted subgraph G -v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G.The deck of G … The vertex-deleted subgraph G -v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G.The deck of G is the multiset of its unlabelled vertexdeleted subgraphs.The number of common cards of G and H is the cardinality of a maximum multiset of common cards, i.e., the multiset intersection of the decks of G and H.We introduce a new approach to the study of common cards using supercards, where we define a supercard G + of G and H to be a graph that has at least one vertex-deleted subgraph isomorphic to G, and at least one isomorphic to H. We show how maximum sets of common cards of G and H correspond to certain sets of permutations of the vertices of a supercard, which we call maximum saturating sets.We then show how to construct supercards of various pairs of graphs for which there exists some maximum saturating set X contained in Aut(G + ).For certain other pairs of graphs, we show that it is possible to construct G + and a maximum saturating set X such that the elements of X that are not in Aut(G + ) are in oneto-one correspondence with a set of automorphisms of a different supercard G + λ of G and H.Our constructions cover nearly all of the published families of pairs of graphs that have a large number of common cards.
Ulam's conjecture, that every graph of order greater than two is determined up to isomorphism by its collection of maximal subgraphs, is verified for the case of separable graphs which … Ulam's conjecture, that every graph of order greater than two is determined up to isomorphism by its collection of maximal subgraphs, is verified for the case of separable graphs which have no pendant vertices.Partial results are then obtained for the case of graphs with pendant vertices.Unless otherwise stated, the graphs dealt with in this paper will be finite and undirected, and may have loops and multiple edges.Any definitions and notation not given below can be found in Berge [1].A part G ι of a graph G is a subset of the vertices and edges of G.The end-vertices of edges in G ι need not themselves be in G\ G -G 1 denotes that partial subgraph of G which is obtained by deleting G 1 and all edges of G which are joined to vertices of G 1 .Now let S be some distinguished set of parts of a graph, and let S(X) -{X 1 } be the labelled set of these parts in the graph X We call two graphs G,ι will be referred to as corresponding parts.In [8] Ulam proposed the following conjecture.CONJECTURE A. Vertex-equivalent graphs of order greater than two are isomorphic.Kelly [7] verified this conjecture for trees and, by exhaustion, for all graphs up to order seven.A related conjecture, intuitively simpler but also as yet unsolved, was suggested by Harary [4].CONJECTURE B. Edge-equivalent graphs with more than three edges are isomorphic.
Abstract The deck of a graph is given by the multiset of (unlabeled) subgraphs . The subgraphs are referred to as the cards of . Brown and Fenner recently showed … Abstract The deck of a graph is given by the multiset of (unlabeled) subgraphs . The subgraphs are referred to as the cards of . Brown and Fenner recently showed that, for , the number of edges of a graph can be computed from any deck missing 2 cards. We show that, for sufficiently large , the number of edges can be computed from any deck missing at most cards.
Abstract The vertex‐deleted subgraph G − v , obtained from the graph G by deleting the vertex v and all edges incident to v , is called a card of … Abstract The vertex‐deleted subgraph G − v , obtained from the graph G by deleting the vertex v and all edges incident to v , is called a card of G . The deck of G is the multiset of its unlabelled vertex‐deleted subgraphs. The number of common cards of G and H (or between G and H ) is the cardinality of the multiset intersection of the decks of G and H . In this article, we present infinite families of pairs of graphs of order n ≥ 4 that have at least \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}2\lfloor\frac{1}{3}(n-1)\rfloor\end{eqnarray*}\end{document} common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n . This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\frac{2}{3}(n+5-2\sqrt{3n+6})\end{eqnarray*}\end{document} common cards, for appropriate values of n , from which we can construct pairs having slightly fewer common cards for all other values of n ≥10. We also present infinite families of pairs of forests and pairs of trees with \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}2\lfloor\frac{1}{3}(n-4)\rfloor\end{eqnarray*}\end{document} and \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}2\lfloor\frac{1}{3}(n-5)\rfloor\end{eqnarray*}\end{document} common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 146–163, 2010