Shuffling the Deck: Invariant Theory and the Graph Reconstruction Conjecture
Emilie Dufresne, Gabriela Jeronimo, Jenny Kenkel, Haydee Lindo, Nelly Villamizar · 2026
Read Shuffling the Deck: Invariant Theory and the Graph Reconstruction Conjecture by Emilie Dufresne, Gabriela Jeronimo, Jenny Kenkel, Haydee Lindo, Nelly Villamizar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16567.txt.
Introduction
Dufresne and colleagues survey the graph reconstruction conjecture in an overview article. The conjecture claims each graph with three or more vertices is fixed by its deck of vertex-deleted subgraphs. Their invariant approach asks whether polynomials telling apart decks also tell apart original graphs. That move turns a graph problem into an algebraic one. The article surveys the conjecture and its algebraic approach for a broad readership.
Catalog record
| CREATOR | Emilie Dufresne, Gabriela Jeronimo, Jenny Kenkel, Haydee Lindo, Nelly Villamizar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38987 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.16567
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Shuffling the Deck: Invariant Theory and the Graph Reconstruction Conjecture Emilie Dufresne, Gabriela Jeronimo, Jenny Kenkel, Haydee Lindo, Nelly Villamizar Abstract The secret graph Imagine there’s a graph. We don’t know what it is, but we have some clues. If a particular vertex is removed from this graph, as well as all the edges connected to that vertex, then we’re left with the graph in Figure 1(a) . (a) The result of removing a specific vertex. (b) Removing either of two other vertices. (c) Removing either of the final two vertices. Figure 1 : The deck of cards for the unknown graph. There are two different vertices in the graph whose removal would each yield the graph in Figure 1(b) . Finally, the last two vertices, when removed, each produce the graph in Figure 1(c) . Can you determine the secret graph? You probably already figured out that the secret graph has five vertices. With a bit more thought, you could determine it must have seven edges (more on this later). At this point, you might take a brute-force approach, considering all ways to add a vertex and two edges to the graph in Figure 1(a) . Eventually, you will find a graph that fits the description (see the end of this paper to have the problem spoiled). But can you be sure what you’ve found is the only graph that works? The graph reconstruction conjecture asserts that you can be sure. It posits that any two graphs with at least three vertices are isomorphic if and only if they have the same collection of isomorphism classes of vertex-deleted subgraphs. We call this multiset of unlabeled subgraphs the deck , and each subgraph is a card . The conjecture claims that every graph is uniquely reconstructible from its deck. For graphs on four vertices, it’s easy to check by hand. There are only 11 non-isomorphic simple graphs, and you can verify that all 11 produce different decks before your coffee gets cold. With a thermos, you can probably check all 34 connected graphs with five vertices. But to check all 156 graphs with six vertices, you’ll need several trips to the microwave. 1 1 1 Just imagine the taste of Brendan McKay’s coffee after checking the conjecture for all 50 trillion graphs with 13 vertices [ 13 ] . This quickly gets out of hand, which is a major reason why the conjecture remains open today. In this article, we will explore how invariant theory provides an elegant framework for studying the graph reconstruction conjecture. The hope of this approach is to show that polynomials that distinguish between decks also distinguish between original graphs, thus translating a graph theoretic problem into an algebraic one. 1 A deck of cards We now make these ideas precise in order to state the graph reconstruction conjecture. We have already defined the deck of a graph as the multiset of its (unlabeled) vertex-deleted subgraphs; each such subgraph is called a card. Let G be a finite simple (undirected) graph with vertex set V(G)=\{v_{1},\ldots,v_{n}\} , indexed by [n]=\{1,\ldots,n\} , and edge set E(G)\subseteq\{\{i,j\}\mid i,j\in[n],~i\neq j\} . A card of G is an unlabeled graph formed by removing one vertex v_{k} of G , k\in[n] , and all the edges adjacent to it, and forgetting the labels of the remaining vertices. That is, a card is the isomorphism class of the vertex-deleted subgraph G_{k} with V(G_{k})=V(G)\setminus\{v_{k}\} and E(G_{k})=E(G)\setminus\{\{i,j\}\mid i=k,\text{ or }j=k\} . The deck of G , written \mathcal{D}(G) , is the multiset of all cards of G . There are n cards in \mathcal{D}(G) , one for each vertex in G . Because the original labels of the vertices have been forgotten in each card, two cards formed from deleting different vertices may be in the same isomorphism class. This is why the deck is defined as a multiset, not a set, because we want to keep track of repeated cards. Example 1.1 . Let G be the graph with n=4 vertices in Figure 2 . v_{1} v_{2} v_{3} v_{4} Figure 2 : An example graph on four vertices. The four subgraphs of G produced by removing a vertex along with all its adjacent edges are in Figure 3 . v_{2} v_{3} v_{4} v_{1} v_{3} v_{4} v_{1} v_{4} v_{2} v_{1} v_{2} v_{3} Figure 3 : The four vertex deleted subgraphs of the graph in Figure 2 . , , , Figure 4 : The deck of the graph in Figure 2 . Let G_{k} denote the graph formed from G by deleting vertex v_{k} . Observe from 3 that G_{1} and G_{4} isomorphic graphs so, the deck of G is the multiset in Figure 4 . \diamond A graph G is called reconstructible if and only if \mathcal{D}(G)=\mathcal{D}(G^{\prime}) implies that G and G^{\prime} are isomorphic graphs. To be reconstructible, a graph must have at least 2 vertices; the two nonisomorphic graphs with two vertices, shown in Figure 5 , have the same deck, shown in Figure 6 . Figure 5 : Nonisomorphic graphs with two vertices which have the same decks. , Figure 6 : The deck of both graphs with two vertices. The graph reconstruction conjecture can be stated as follows. Conjecture 1.2 ( [ 10 ] and [ 19 ] ) . For n\geqslant 3 , every simple undirected n -vertex graph is reconstructible. 2 What the deck reveals Reading a graph’s deck is like reading a hand of cards: some information is immediately visible, while other properties require more work. In this section we explore what can be determined from \mathcal{D}(G) alone. 2.1 Cards on the table From the deck, the most apparent information about the original graph is the number of vertices: it equals the number of cards in \mathcal{D}(G) , or equivalently, one more than the number of vertices in any single card. The number of edges |E(G)| can also be recovered. Each edge of G is absent from exactly two cards in the deck, namely those obtained by deleting each of its endpoints, and therefore appears in exactly n-2 cards. It follows that |E(G)|=\frac{\sum_{k=1}^{n}|E(G_{k})|}{n-2}, where the sum runs over all cards G_{k} in the deck. This immediately settles the reconstruction conjecture for any class of graphs in which the number of edges determines the graph’s isomorphism class: these include complete graphs (every pair of vertices connected), almost complete graphs (exactly one edge missing), empty graphs, and graphs with exactly one edge. A reference for reconstructability of these and other families of graphs is [ 12 ] . From the deck, we can also recover the degree of each vertex. Recall that the degree \deg(v_{k}) of a vertex v_{k}\in V(G) is the number of edges that are incident to v_{k} . Since deleting v_{k} removes precisely its incident edges, then we have \deg(v_{k})=|E(G)|-|E(G_{k})|, where G_{k} is the card obtained by deleting v_{k} . We illustrate this with our earlier example (Figure 3 ). The deck has 4 cards, so G has 4 vertices. The cards have 3,2,2 and 1 , edges respectively, giving |E(G)|=\frac{3+2+2+1}{4-2}=4. Subtracting each card’s edge count |E(G)| from the total number of edges then yields the degree of the corresponding deleted vertex, and so the degree multiset