Degree Lists and Connectedness are 3-Reconstructible for Graphs with At Least Seven Vertices

Abstract

The k-deck of a graph is the multiset of its subgraphs induced by k vertices. A graph or graph property is l-reconstructible if it is determined by the deck of subgraphs obtained by deleting l vertices. We show that the degree list of an n-vertex graph is 3-reconstructible when $n\ge 7$, and the threshold on n is sharp. Using this result, we show that when $n\ge 7$ the $(n-3)$-deck also determines whether an n-vertex graph is connected; this is also sharp. These results extend the results of Chernyak and Manvel, respectively, that the degree list and connectedness are 2-reconstructible when $n\ge 6$, which are also sharp.

1 Introduction

A card of a graph G is a subgraph of G obtained by deleting one vertex. Cards are unlabeled, so only the isomorphism class of a card is given. The deck of G is the multiset of all cards of G. A graph is reconstructible if it is uniquely determined by its deck. The famous Reconstruction Conjecture was first posed in 1942.

Conjecture 1.1

(The Reconstruction Conjecture; Kelly [8, 9], Ulam [21]) Every graph having more than two vertices is reconstructible.

The two graphs with two vertices have the same deck. Graphs in many families are known to be reconstructible; these include disconnected graphs, trees, regular graphs, and perfect graphs. Surveys on graph reconstruction include [3, 4, 10–12].

Various parameters have been introduced to measure the difficulty of reconstructing a graph. Harary and Plantholt [7] defined the reconstruction number of a graph to be the minimum number of cards from its deck that suffice to determine it, meaning that no other graph has the same multiset of cards in its deck (surveyed in [1, 16]). Kelly looked in another direction, considering cards obtained by deleting more vertices. He conjectured a more detailed version of the Reconstruction Conjecture.

Conjecture 1.2

(Kelly [9]) For $l\in {{\mathbb {N}}}$, there is an integer$M_l$such that any graph with at least$M_l$vertices is reconstructible from its deck of cards obtained by deletinglvertices.

The original Reconstruction Conjecture is the claim $M_1=3$.

A k-card of a graph is an induced subgraph having k vertices. The k-deck of G, denoted ${{\mathcal {D}}}_k(G)$, is the multiset of all k-cards. When discussing reconstruction from the k-deck, we will refer to k-cards simply as cards.

Definition 1.3

A graph G is k-deck reconstructible if ${{\mathcal {D}}}_k(H)={{\mathcal {D}}}_k(G)$ implies $H\cong G$. A graph G (or a graph invariant) is l-reconstructible if it is determined by ${{\mathcal {D}}}_{|V(G)|-l}(G)$ (agreeing on all graphs having that deck). The reconstructibility of G, written $\rho (G)$, is the maximum l such that G is l-reconstructible.

For an n-vertex graph, “k-deck reconstructible” and “l-reconstructible” have the same meaning when $k+l=n$. Kelly’s conjecture is that for any $l\in {{\mathbb {N}}}$, all sufficiently large graphs are l-reconstructible. Let $K'_{1,3}$ and $K''_{1,3}$ be the graphs obtained from the claw $K_{1,3}$ by subdividing one or two edges, respectively. The 5-vertex graphs $C_4+K_1$ and $K'_{1,3}$ are not 2-reconstructible, since they have the same 3-deck. Having checked by computer that every graph with at least six and at most nine vertices is 2-reconstructible, McMullen and Radziszowski [14] asked whether $M_2=6$. With computations up to nine vertices, Rivshin and Radziszowski [18] conjectured $M_l\le 3l$. However, Nýdl [17] disproved this, showing that $M_\ell$, if it exists, must grow faster than linear.

Some results about reconstruction have been extended to the context of reconstruction from the k-deck. For example, almost every graph is reconstructible from any set of three cards in the deck of cards obtained by deleting one vertex (see [2, 6, 15]). Müller [15] proved more generally that for $l=(1-o(1))|V(G)|/2$, almost all graphs are l-reconstructible; Spinoza and West [19] showed that only $\left( {\begin{array}{c}l+2\\ 2\end{array}}\right)$ cards are needed for this. In [19], they also determined $\rho (G)$ exactly for every graph G with maximum degree at most 2.

Since each induced subgraph with $k-1$ vertices arises exactly $n-k+1$ times by deleting one vertex from a member of ${{\mathcal {D}}}_k(G)$, we have the following.

Observation 1.4

For any graph G, the k-deck ${{\mathcal {D}}}_k(G)$ determines the $(k-1)$-deck ${{\mathcal {D}}}_{k-1}(G)$.

By Observation 1.4, information that is k-deck reconstructible is also j-deck reconstructible when $j>k$. This motivates the definition of reconstructibility; if G is l-reconstructible, then G is also $(l-1)$-reconstructible, so we seek the largest such l.

Manvel [13] proved for $n\ge 6$ that the $(n-2)$-deck of an n-vertex graph determines whether the graph satisfies the following properties: connected, acyclic, unicyclic, regular, and bipartite. For the first three of these properties, sharpness of the threshold on n is shown by the graphs $C_4+P_1$ and $K'_{1,3}$ mentioned above. Spinoza and West [19] extended Manvel’s result by showing that connectedness is 3-reconstructible when $n\ge 25$. Using a somewhat different approach, we extend their result.

Theorem 1.5

For$n\ge 7$, connectedness is 3-reconstructible forn-vertex graphs, and the threshold onnis sharp.

The threshold is sharp because $C_5+P_1$ and $K''_{1,3}$ have the same 3-deck. For general l, the known upper and lower bounds on the threshold for n to guarantee that connectedness of n-vertex graphs is l-reconstructible are quite far apart. Spinoza and West [19] proved that connectedness is l-reconstructible when $n>2l^{(l+1)^2}$. As a lower bound, we know only that $n>2l$ is needed, since $C_{l+1}+P_{l-1}$ and $P_{2l}$ have the same l-deck [19]. Indeed, $P_n$ is the only n-vertex graph whose reconstructibility is known to be less than n/2.

One of the first easy results in ordinary reconstruction is that the degree list of a graph with at least three vertices is 1-reconstructible. Manvel [13] showed that the degree list is reconstructible from the k-deck when the maximum degree is at most $k-2$. With no restriction on the maximum degree, Taylor showed that the degree list is reconstructible from the k-deck when the number of vertices is not too much larger than k, regardless of the value of the maximum degree.

Theorem 1.6

(Taylor [20]) If$l\ge 3$and$n\ge g(l)$, then the degree list of anyn-vertex graph is determined by its$(n-l)$-deck, where

$$\begin{aligned} g(l) = (l+\log {l}+1) \left( \mathrm{e}+ \frac{\mathrm{e}\log {l} + \mathrm{e}+1}{(l-1) \log {l}-1} \right) +1 \end{aligned}$$

and$\mathrm{e}$denotes the base of the natural logarithm. Thus the degree list isl-reconstructible when$n>\mathrm{e}l+O(\log l)$.

For small l, one can obtain exact thresholds. Chernyak [5] proved that the degree list is 2-reconstructible when $n\ge 6$; again the example of $C_4+P_1$ and $K'_{1,3}$ shows that this is sharp. We extend this to 3-reconstructibility.

Theorem 1.7

For$n\ge 7$, any two graphs of ordernthat have the same$(n-3)$-deck have the same degree list, and this threshold onnis sharp.

Again the example of $C_5+P_1$ and $K''_{1,3}$ proves sharpness. We use Theorem 1.7 as a tool in the proof of Theorem 1.5. With Chernyak’s result being somewhat inaccessible, we also obtain it and Manvel’s result on 2-reconstructibility of connectedness as corollaries of our results.

2 3-Reconstructibility of Degree Lists

We begin with a basic counting tool used also by Manvel [13] and by Taylor [20]. In a graph G, we refer to a vertex of degree j as a j-vertex.

Lemma 2.1

Let$\phi (j)$denote the total number ofj-vertices over all cards in thek-deck ${{\mathcal {D}}}_k$of ann-vertex graphG. Letting$a_i$denote the number ofi-vertices inG (and$l=n-k$),

$$\begin{aligned} \phi (j)=\sum _{i=j}^{j+l} a_i\left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}n-1-i\\ k-1-j\end{array}}\right) . \end{aligned}$$

(1)

Proof

In each card, each vertex counted by $\phi (j)$ has degree at least j in G. When that degree is i, the vertex in the reconstructed graph contributes exactly $\left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}n-1-i\\ k-1-j\end{array}}\right)$ to the computation of $\phi (j)$. This contribution is 0 when $k-1-j> n-1-i$; the vertex then does not have enough nonneighbors in the full graph to occur with degree exactly j in a card. Thus we require $i\le n-k+j=l+j$. $\square$

Corollary 2.2

(Manvel [13]) From thek-deck of a graph and the numbers of vertices with degreeifor all iat leastk, the degree list of the graph is determined.

Proof

Since the k-deck determines the $(k-1)$-deck, using induction it suffices to show that knowing both ${{\mathcal {D}}}_k(G)$ and $a_i$ for $i\ge k$ determines $a_{k-1}$. Simply solve for $a_{k-1}$ in the expression (1) for $\phi (k-1)$ obtained by setting $j=k-1$. $\square$

With these tools, we prove Theorem 1.7, which we repeat for convenience.

Theorem (1.7)

For$n\ge 7$, any two graphs of ordernthat have the same$(n-3)$-deck have the same degree list, and this threshold onnis sharp.

Proof

For sharpness, the 3-decks of both $C_5+K_1$ and $K''_{1,3}$ consist of five copies of $P_3$, ten copies of $P_2+P_1$, and five copies of $3P_1$.

Given $n\ge 7$, let ${{\mathcal {D}}}$ be the $(n-3)$-deck of an n-vertex graph. We show that all reconstructions from ${{\mathcal {D}}}$ have the same degree list.

Let G and H be reconstructions from ${{\mathcal {D}}}$. Since ${{\mathcal {D}}}$ determines the 2-deck, we know the common number of edges in G and H; let it be m. We may assume $m\le \frac{1}{2} { \left( {\begin{array}{c}n\\ 2\end{array}}\right)}$, since otherwise we can analyze the complements of G and H.

We will use repeatedly the fact that any t vertices whose degrees sum to at least s are together incident to at least $s-{ \left( {\begin{array}{c}t\\ 2\end{array}}\right)}$ edges.

Let $a_i$ and $b_i$ be the numbers of i-vertices in G and H, respectively, and let $c_i=a_i-b_i$. The computation in (1) is valid using either G or H, producing the same value $\phi (j)$ from ${{\mathcal {D}}}$. Hence the difference of the two instances of (1) yields

$$\begin{aligned} 0=\sum _{i=j}^{j+3} c_i\left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}n-1-i\\ n-4-j\end{array}}\right) , \end{aligned}$$

(2)

since here $k=n-3$. We will be interested in particular in the cases $j=n-4$ (dominating vertices on cards) and $j=n-5$, which we write explicitly as

$$\begin{aligned} c_{n-4}+(n-3)c_{n-3}+\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) c_{n-2}+\left( {\begin{array}{c}n-1\\ 3\end{array}}\right) c_{n-1}=0 \end{aligned}$$

(3)

and

$$\begin{aligned} 4c_{n-5}+3(n-4)c_{n-4}+2\left( {\begin{array}{c}n-3\\ 2\end{array}}\right) c_{n-3}+\left( {\begin{array}{c}n-2\\ 3\end{array}}\right) c_{n-2}=0. \end{aligned}$$

(4)

The observation of Manvel (Corollary 2.2) implies that if G and H have different degree lists, then $c_i\ne 0$ for some i with $i\ge n-3$. Let h be the largest such index. By symmetry, we may assume $c_h<0$. We consider cases depending on the value of h.

Case 1:$h=n-3$. In this case $c_{n-1}=c_{n-2}=0$ and $c_{n-3}<0$. By (3), $c_{n-4}+(n-3)c_{n-3}=0$. Since $2(n-3)>n$ when $n\ge 7$, we have $c_{n-3}=-1$ and $c_{n-4}=n-3$. Now (4) implies $c_{n-5}=-(n-3)(n-4)/2$. Thus H has at least $1+(n-3)(n-4)/2$ vertices, but $n\ge 1+(n-3)(n-4)/2$ requires $n\le 7$. Hence $n=7$ and H has degree list exactly (4, 2, 2, 2, 2, 2, 2), and G has no vertices of degree 2 or at least 4. Furthermore $c_{n-4}=n-3$, so G has exactly four vertices with degree 3 and cannot reach the same degree-sum as H.

Case 2:$h=n-2$. Now $c_{n-1}=0$ and $c_{n-2}<0$. Let $c_{n-2}=-r$. By (3), $c_{n-4}+{(n-3)c_{n-3}}=r\left( {\begin{array}{c}n-2\\ 2\end{array}}\right)$, so $\frac{c_{n-4}}{n-3}+c_{n-3}=(n-2)\frac{r}{2}$. With $r\ge 2$ and $n\ge 7$ and $c_{n-4}+c_{n-3}\le n$, this can only be satisfied when $r=2$, $c_{n-3}=n-2$, and $c_{n-4}=0$. Since $m\le \frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$, the degree-sum is at most $\left( {\begin{array}{c}n\\ 2\end{array}}\right)$; hence $(n-2)(n-3)\le \frac{1}{2} n(n-1)$, which requires $n<8$. Since we have obtained $(c_5,c_4,c_3)=(-2,5,0)$, (4) yields $4c_2=\left( {\begin{array}{c}5\\ 3\end{array}}\right) \cdot 2-2\left( {\begin{array}{c}4\\ 2\end{array}}\right) \cdot 5=-40$; this requires $c_2=-10$, a contradiction when $n=7$. Hence we conclude $r=1$.

With $r=1$, we have $c_{n-4}+(n-3)c_{n-3}=\left( {\begin{array}{c}n-2\\ 2\end{array}}\right)$. Hence

$$\begin{aligned} c_{n-3}=\frac{n-2}{2}-\frac{c_{n-4}}{n-3}. \end{aligned}$$

(5)

Substituting into (4) yields

$$\begin{aligned} 4c_{n-5}&=\left( {\begin{array}{c}n-2\\ 3\end{array}}\right) -2\left( {\begin{array}{c}n-3\\ 2\end{array}}\right) c_{n-3}-3(n-4)c_{n-4}\nonumber \\&=-\frac{(n-2)(n-3)(n-4)}{3}-2(n-4)c_{n-4} \end{aligned}$$

(6)

Since $c_{n-3}$ must be an integer, by (5) there are not many possibilities for $c_{n-4}$. Let $t=\frac{c_{n-4}}{n-3}$. Since $\left| c_{n-4} \right| \le n$, we have $t\in \{1,0,-1\}$ when n is even, and $t\in \{1/2,-1/2\}$ when n is odd. Also (6) simplifies to $-c_{n-5}=\frac{(n-3)(n-4)}{12}[n-2+6t]$.

With $c_{n-5}\ge -n$ and $n\ge 7$, the possibilities that remain for (n, t) are $(7,-1/2)$, $(8,-1)$, and $(10,-1)$. Note that $c_{n-3}=\frac{n-2}{2}-t$. In the even cases, $c_{n-3}=n/2$. When $n=10$, five 7-vertices are together incident to at least 25 edges, which is more than $\frac{1}{2}\left( {\begin{array}{c}10\\ 2\end{array}}\right)$.

When $n=8$, four 5-vertices in G are together incident to at least 14 edges, which is the maximum allowed, so there can be no other edges or other 5-vertices, the four 5-vertices induce $K_4$, and eight edges join these vertices to the rest. Since $c_{n-4}=-5$, in H the vertices of degree at least 4 already contribute 26 to the degree-sum, so H has no 3-vertex. With $c_{n-5}=0$, also G has no 3-vertex. Hence the degree list of G is (5, 5, 5, 5, 2, 2, 2, 2). With $(c_5,c_4,c_3)=(4,-5,0)$, applying (2) with $j=2$ now yields $c_2=5$, a contradiction.

When $n=7$, we have $t=-1/2$, and $(c_2,c_3,c_4,c_5,c_6)=(-2,-2,3,-1,0)$. Hence $\sum _{i=2}^{6} ic_i= -3$, and having equal degree-sum requires $c_1=3$. Now H has six vertices with degrees (5, 3, 3, 2, 2, 0) and G has six vertices with degrees (4, 4, 4, 1, 1, 1), and they each have one more vertex of the same odd degree. Since the degree list of G must be realizable, the only choice is (4, 4, 4, 3, 1, 1, 1) for G and (5, 3, 3, 3, 2, 2, 0) for H. Now G is realized only by adding three pendant edges to $K_4$, so $K_4$ is a card in ${{\mathcal {D}}}$, which can be obtained from H only on the four vertices of high degree. Thus H consists of copies of $K_4$ and $K_3$ sharing one vertex, plus an isolated vertex. Being the union of three complete graphs, H has no independent set of size 4, but G does have such a set, so their 4-decks cannot be equal.

Case 3:$h=n-1$. If $c_{n-2}\ge \frac{n+1}{3}$, then $m\ge \frac{n+1}{3}(n-2)-\frac{1}{2}\frac{n+1}{3}\frac{n-2}{3}=\frac{5}{18}(n+1)(n-2)$. Since this exceeds $\frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ when $n\ge 7$, we conclude $c_{n-2}\le n/3$.

Let $r=-c_{n-1}$. If $r\ge 2$, then (3) and $c_{n-2}\le n/3$ together yield $c_{n-4}+(n-3)c_{n-3}\ge 2\left( {\begin{array}{c}n-1\\ 3\end{array}}\right) -\frac{n}{3}\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) =\frac{(n-2)^2(n-3)}{6}$. The contribution to degree-sum in G from vertices of degrees $n-4$ and $n-3$ is now at least $\frac{(n-2)^2(n-3)}{6}$, which exceeds $\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ when $n\ge 8$. Hence $n=7$, but then having two 6-vertices in H requires at least 11 edges (more than $\frac{1}{2}\left( {\begin{array}{c}7\\ 2\end{array}}\right)$), a contradiction. Thus we may assume $r=1$.

With $r=1$, (3) yields $c_{n-4}+(n-3)c_{n-3}+\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) c_{n-2}=\left( {\begin{array}{c}n-1\\ 3\end{array}}\right)$. If $c_{n-2}\le 0$, then $c_{n-4}+(n-3)c_{n-3}\ge \left( {\begin{array}{c}n-1\\ 3\end{array}}\right)$. Dividing by $n-3$ and using $c_{n-4}+c_{n-3}\le n$ yields $n\ge \frac{(n-1)(n-2)}{6}$, which requires $n<9$. If $n=8$, then $c_6\le 0$ simplifies (3) to $c_4+5c_5\ge 35$, but $a_i\ge c_i$ and $m\le \frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ yield $28\ge 4a_4+5a_5\ge c_4+5c_5$. If $n=7$, then (3) simplifies to $c_3+4c_4\ge 20$, but $m\le 10$ yields $3a_3+4a_4\le 20$. Since $a_i\ge c_i$, we conclude $c_3\le 0$ and $c_4\ge 5$. With at most 10 edges, $G=K_5+2K_1$. Now ${{\mathcal {D}}}$ has five cards that are $K_4$. With only four edges not incident to its dominating vertex, H cannot have five such cards. We conclude $c_{n-2}\ge 1$.

With $a_{n-2}\ge c_{n-2}\ge 1$, we now break into subcases by the value of $c_{n-2}$. We have already proved $c_{n-2}\le n/3$. Let $x=\frac{n-1}{3}-c_{n-2}$, so $x\ge -1/3$ and (3) yields

$$\begin{aligned} c_{n-4}+(n-3)c_{n-3}=x\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) . \end{aligned}$$

(7)

Substituting (7) into (4) yields

$$\begin{aligned} c_{n-5}=\frac{1}{72}(n-3)(n-4)[36c_{n-3}-(n-2)(24x+n-1)]. \end{aligned}$$

(8)

Subcase 3.1:$x\ge 1$. If $c_{n-3}\ge \frac{n-2}{2}$, then with $a_{n-2}\ge 1$ the vertices of degrees $n-2$ and $n-3$ in G are incident to at least $\frac{n-2}{2}(n-3)+(n-2)-\left( {\begin{array}{c}n/2\\ 2\end{array}}\right)$ edges. Hence $m\ge \frac{(n-2)(3n-4)}{8}$; this exceeds $\frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ when $n\ge 7$. If $c_{n-3}\le \frac{n-3}{2}$, then $c_{n-4}\ge \left( {\begin{array}{c}n-2\\ 2\end{array}}\right) -(n-3)\frac{n-3}{2}=\frac{n-3}{2}$, by (7). Also $c_{n-3}\ge 1$, since otherwise (7) yields $c_{n-4}\ge \left( {\begin{array}{c}n-2\\ 2\end{array}}\right) \ge n$. If $a_{n-3}=1$, then $c_{n-4}\ge \left( {\begin{array}{c}n-2\\ 2\end{array}}\right) -(n-3)=\frac{(n-3)(n-4)}{2}$, again too many vertices when $n\ge 7$ (since $a_{n-2}\ge 1$).

Hence $a_{n-3}\ge 2$. Now $m\ge {\frac{n+3}{2}}(n-4)+4-\left( {\begin{array}{c}(n+3)/2\\ 2\end{array}}\right)$. This quantity exceeds $\frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ when $n\ge 9$. For $n=8$, we have $a_4\ge 3$, $a_5\ge 2$, $a_6\ge 1$, yielding degree-sum already 28, so G has degree list (6, 5, 5, 4, 4, 4, 0, 0), but degree 6 forbids two isolated vertices. For $n=7$, we have $a_{n-4}\ge 2$, so even degree-sum at most 20 requires degree list (5, 4, 4, 3, 3, 1, 0). To avoid higher degree-sum, $a_i=c_i$ for $i\in \{5,4,3,1\}$. Hence $b_i=0$ for these values. Now H having one 6-vertex requires $b_2=7$ to reach degree-sum 20, contradicting $n=7$.

Subcase 3.2:$x\in \{\frac{2}{3},\frac{1}{3}\}$. If $c_{n-3}\le 2$, then $c_{n-5}<-n$ when $n\ge 9$ by (8), a contradiction. If $x=\frac{2}{3}$, then $c_{n-2}=\frac{n-3}{3}\in {{\mathbb {N}}}$, so $n\ge 9$. If $x=\frac{1}{3}$, then $c_{n-2}=\frac{n-2}{3}\in {{\mathbb {N}}}$, so $n\ge 8$. Setting $n=8$ and $x=\frac{1}{3}$ and $c_{n-3}\le 1$ in (8) yields $c_{n-5}\le -15$, so $c_{n-3}=2$. Now (7) yields $c_{n-4}+5\cdot 2=5$, so $c_4=-5$. With $c_3+3c_4+5c_5+5c_6=0$ by (4), we have $c_3=-5$. Now H has at least 10 vertices, a contradiction.

Hence $c_{n-3}\ge 3$. Since also $c_{n-2}\ge \frac{n-3}{3}$, the number of edges in G incident to vertices of degree at least $n-3$ is at least $\frac{n+6}{3}(n-2)-3-\left( {\begin{array}{c}(n+6)/3\\ 2\end{array}}\right)$, which simplifies to $\frac{5}{18}(n+6)(n-3)-3$ and is more than $\frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ when $n\ge 8$.

Subcase 3.3:$x=0$. Note that $c_{n-2}=\frac{n-1}{3}\in {\mathbb {Z}}$. By (7), $c_{n-4}=-(n-3)c_{n-3}$, so $-1\le c_{n-3}\le 1$. By (8), $c_{n-5}= \frac{(n-3)(n-4)}{72}[36c_{n-3}-(n-1)(n-2)]$. With $c_{n-3}\le 1$, this yields $c_{n-5}<-n$ when $n\ge 10$, a contradiction. Since $c_{n-2}\equiv 1\mod 3$, only $n=7$ remains.

With $n=7$, the expressions above reduce to $c_5=2$, $c_3=-4c_4$, and $c_2=6c_4-5$, with $-1\le c_4\le 1$. If $c_4=-1$, then $c_2=-11<-7$. If $c_4=1$, then G has three vertices of degrees 4 and 5 such that the number of edges incident to them is at least $3\cdot 4+2-\left( {\begin{array}{c}3\\ 2\end{array}}\right)$, which equals 11 and exceeds $\frac{1}{2}\left( {\begin{array}{c}7\\ 2\end{array}}\right)$.

The remaining case is $c_4=c_3=0$ and $c_2=-5$, also $c_5=2$ and $c_6=-1$. Since we know the 2-deck, G and H have the same degree-sum; that is, $\sum _{i=0}^{6} ic_i=0$. We have $\sum _{i=0}^{6} ic_i = c_1-10+10-6$; hence $c_1=6$. Now $a_5\ge 2$ and $a_1\ge 6$, which contradicts $n=7$.

Subcase 3.4:$x=-\frac{1}{3}$. Here $c_{n-2}=\frac{n}{3}$, so $n\ge 9$. The number of edges incident to vertices of degree at least $n-2$ in G is at least $\frac{n}{3}(n-2)-\frac{1}{2}\frac{n}{3}\frac{n-3}{3}$, which exceeds $\frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ when $n>9$ and equals it when $n=9$. For $n=9$ with $x=-\frac{1}{3}$, (7) reduces to $c_{5}+6c_6=-7$ and (8) reduces to $c_4=15c_6$, which requires $c_6=0$. Hence $b_5\ge -c_5=7$, which with $b_8=1$ gives H degree-sum at least 43, contradicting $m=18$. $\square$

Using Theorem 1.7, we present an alternative proof of the result by Chernyak on the threshold for 2-reconstructibility of the degree list.

Corollary 2.3

(Chernyak [5]) The degree list of an n-vertex graph is 2-reconstructible whenever$n\ge 6$, and this is sharp.

Proof

Since the $(n-2)$-deck determines the $(n-3)$-deck, it is immediate from Theorem 1.7 that the degree list is 2-reconstructible when $n\ge 7$. By the example of $C_4+K_1$ and $K'_{1,3}$, $n\ge 5$ is not sufficient. It remains only to consider $n=6$.

Let G and H be two 6-vertex graphs having the same 4-deck ${{\mathcal {D}}}$ but different degree lists. Let $m=\left| E(G) \right| =\left| E(H) \right|$ (we know the 2-deck). Since the k-deck determines the k-deck of the complement and $\left( {\begin{array}{c}6\\ 2\end{array}}\right) =15$, we may assume $m\le 7$. Define $a_i,b_i,c_i,h$ as in Theorem 1.7. That is, with $k=4$, different degree lists in G and H require a largest h with $h\ge k$ such that $a_h\ne b_h$, and by symmetry we have $c_h=a_h-b_h<0$. We use the equation for $\phi (3)$, which counts dominating vertices in the cards of the 4-deck:

$$\begin{aligned} c_{3}+4c_4+10c_5=0 . \end{aligned}$$

(9)

Case 1:$h=5$. We have $-c_5=1$, because two 5-vertices in H already force $m\ge 9$. Thus $4c_4+c_3=10$, by (9). If $c_4\ge 3$, then $m\ge 3\cdot 4-\left( {\begin{array}{c}3\\ 2\end{array}}\right) =9$. If $c_4=2$, then also $c_3=2$ and $m\ge 2\cdot 4+2\cdot 3-\left( {\begin{array}{c}4\\ 2\end{array}}\right) =8$. However, $m\le 7$. If $c_4<2$, then G has too many vertices.

Case 2:$h=4$. Here $c_3=-4c_4$. With $n=6$, we have $c_4=-1$ and $c_3=4$. With degree-sum at most 14, the degree list of G is (3, 3, 3, 3, x, y) with $(x,y)\in \{(2,0),(1,1),(0,0)\}$. Thus also $b_4=1$ and $b_3=0$, so H has only one vertex with degree exceeding 2. If $(x,y)=(0,0)$, then $G=K_4+2K_1$ and $K_4$ is a card, but $K_4$ is not contained in H.

Hence $m=7$, and the degree list of H must be (4, 2, 2, 2, 2, 2). The only such graph consists of a 4-cycle and a 3-cycle with one common vertex. Every card of H has at most four edges. Whether (x, y) is (1, 1) or (2, 0), deleting from G the two vertices of smallest degree eliminates at most two edges and leaves a card with five edges, a contradiction. $\square$

3 3-Reconstructibility of Connectedness

Using Theorem 1.7, we prove Theorem 1.5. Again the example of $C_5+P_1$ and $K''_{1,3}$ shows that the threshold on $n\ge 7$ is sharp; they have the same 3-deck, but only one is connected.

Theorem (1.5)

For$n\ge 7$, connectedness is 3-reconstructible forn-vertex graphs, and the threshold onnis sharp.

Proof

Suppose that n-vertex graphs G and H have the same $(n-3)$-deck ${{\mathcal {D}}}$, but that G is connected and H is disconnected. Let m be the common number of edges in G and H. Let C be the largest component in H. Since G is connected, it has a spanning tree T. Since $n\ge 7$, T has at least two connected cards. Thus ${{\mathcal {D}}}$ has at least two connected cards, so C has at least $n-2$ vertices.

By Theorem 1.7, G and H have the same degree list. Since G is connected, H cannot have an isolated vertex, so $H=C+K_2$. If C has a 1-vertex, then deleting it and the vertices of the small component in H leaves a card in D with $m-2$ edges. However, since G is connected, it is not possible to delete three vertices in G and only remove two edges. Hence C has no 1-vertex, which means that G and H each have exactly two 1-vertices. Let u and v be the 1-vertices in G, and let Y be the set of 1-vertices in H.

Let x be the number of 2-vertices in both G and in H. If $x=0$, then C has minimum degree at least 3. Deleting Y and one vertex of C from H now yields $n-2$ cards with minimum degree at least 2. Such cards can arise from G only by deleting the two 1-vertices and one other vertex. Hence $G-\{u,v\}$ and C have the same $(n-3)$-deck. They must therefore have the same number of edges. However, C has $m-1$ edges, while $G-\{u,v\}$ has $m-2$ edges. Thus $x>0$.

To eliminate only three edges from H when deleting three vertices, one must delete Y and a 2-vertex of C. Thus x is also the number of cards in ${{\mathcal {D}}}$ with $m-3$ edges. We show the remaining possibilities for G in Fig. 1.

Fig. 1

Possibilities for G in Theorem 1.5

If u and v have the same neighbor, w, then G can have a card with $m-3$ edges only if w has degree 3 and the deleted set is $\{u,v,w\}$. Hence in this case $x=1$.

If u and v have different neighbors, then each of u and v is the end of a maximal path containing no vertices of degree larger than 2 in G; call these paths P(u) and P(v). We can only obtain a card with $m-3$ edges by deleting i vertices from P(u) and j vertices from P(v), where $i+j=3$. There are at most four choices for i, so $x\le 4$. In order to have exactly x cards with $m-3$ edges, there must be a total of x vertices of degree 2 on $P(u)\cup P(v)$ and hence no 2-vertices elsewhere in G (see Fig. 1).

Now consider the cards of G obtained by removing three vertices. When $x\ge 2$, the paths P(u) and P(v) together have at least four vertices of degree at most 2, so removing any three vertices of G leaves a vertex of degree at most 1. Hence removing Y and a vertex of C from H must also leave a vertex of degree at most 1. This means that every vertex of C has a neighbor of degree 2. In the two possibilities when $x=1$, the one card of G with $m-3$ edges may have no vertex of degree at most 1, but all other cards must have such a vertex. In this case every vertex of C except possibly one has a neighbor of degree 2.

For $x\in \{3,4\}$, label u and v so that $|V(P(u))|\ge |V(P(v))|$. Consider a card D of G with $m-3$ edges that is obtained by deleting u, v and the neighbor of u, so D has two vertices of degree 1 and $x-3$ vertices of degree 2. Since all 2-vertices in G are in $P(u)\cup P(v)$, the other vertices in D have degree at least 3. Note that D must be a vertex-deleted subgraph of C, since cards with $m-3$ edges are obtained from H only by deleting Y and a vertex of C. Since C must have x vertices of degree 2 and none of degree 1, it must be formed from D by adding one vertex z of degree 2 whose neighbors are the two 1-vertices in D. Adding z to form C shows that the 2-vertices in C lie along a single path. This means that only two vertices outside this path can have neighbors of degree 2. Since every vertex of C must have a neighbor of degree 2, we conclude that C has at most two vertices outside the path, but then those vertices cannot have degree greater than 2, a contradiction.

When $x=2$, recall that every vertex in C has a neighbor of degree 2 (including the vertices of degree 2). Each vertex of degree 2 is a neighbor of only two vertices. Hence $2=x\ge (n-2)/2$, so $n\le 6$. Similarly, when $x=1$, all but one vertex of C has a neighbor of degree 2, so $1=x\ge (n-3)/2$, yielding $n\le 5$.

We have obtained contradictions in all cases, so such G and H do not exist. $\square$

Using Theorem 1.5, Manvel’s result on 2-reconstructibilty of connectedness follows quite easily.

Corollary 3.1

(Manvel [13]) For $n\ge 6$, connectedness of ann-vertex graph is 2-reconstructible.

Proof

Again $C_4+K_1$ and $K'_{1,3}$ give sharpness, and Theorem 1.5 handles $n\ge 7$. Consider connected and disconnected 6-vertex graphs G and H with the same 4-deck.

By Corollary 2.3, G and H have the same degree list, so neither has isolated vertices. Since G has a connected 4-card, H has a 4-vertex component C, and $H=C+K_2$. Thus H has only one connected 4-card.

Now G must also have only one connected 4-card. Therefore every spanning tree of G is a path, so G is a path, but then G has three connected 4-cards. $\square$