Reconstruction of Graphs

Abstract

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.

1. Introduction

Probably the foremost unsolved problem in Graph Theory is Ulam’s Conjecture. This problem is due to P.J. Kelly and S.M. Ulam. Kelly’s Ph.D thesis [1] written under S.M.Ulam in 1942 dealt with this. Ulam proposed it as a set theory problem in his famous book “A Collection of Mathematical Problems” [2].

This is how Ulam’s problem was originally stated [2]:

Suppose that $E$ and $F$ are two sets, each containing $m$ elements such that there is defined a distance function $\mu$ for every pair of distinct points, with values either $1$ or $2$, and $\mu \left(p,p\right)=0$. If, for every subset of $n-1$ points of $E$, there exists an isometric system of $m-1$ points of $F$ and the number of distinct subsets isometric to any given subset of $m-1$ points is the same in $E$ and in $F,$ then does $E$ and $F$ isometric?

There are many restatements of Ulam’s original conjecture, each dealing with another way of talking about sets. Kelly [3] has given the graph theoretic version of this problem as below and solved it for trees and disconnected graphs, and verified it for graphs on up to six vertices.

Theorem 1.1.(Ulam Conjecture).

Let $G$ and $H$ be graphs with $V\left(G\right)=v_1,v_2,\cdots ,v_n$ and for $n\ge 3$. If $G-v_i\cong H-u_i,$ for all then $G\cong H$.

Many graph theorists have found other ways to restate the Ulam Conjecture. But the current version of this problem, popularly known as the Reconstruction Conjecture is the one formulated by Frank Harary [4].

Theorem 1.2. (Reconstruction Conjecture).

Every graph on at least three vertices is uniquely determined up to isomorphism by the collection of its one vertex-deleted subgraphs.

Graphs obeying the above conjecture are said to be reconstructible. Many classes of graphs and some parameters of graphs are already proved to be reconstructible. The papers [5, 6] and the book [7] deal with earlier work done on this problem. P. J. Kelly first proved that trees are reconstructible; but the proof is quite lengthy. A short proof was given by Greenwell and Hemminger using a powerful but simple 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.

2. Reconstructible parameters and graphs

A vertex-deleted subgraph of a graph $G,$ is called a card of $G$. The collection of all cards of $G$ is called the deck of $G$ and is denoted by $\mathcal{D}\left(G\right)$.

Note that the graphs in the deck are unlabelled and, if G contains isomorphic vertex-deleted subgraphs, then such subgraphs are repeated in $\mathcal{D}\left(G\right)$ according to the number of isomorphic subgraphs that $G$ contains. Therefore $\mathcal{D}\left(G\right)$ is a multiset, rather than a set, of isomorphism type of graphs.

Figure 1 shows an example of a graph and its deck.

Figure 1.

Graph and its deck.

A graph $H$ with deck $\mathcal{D}\left(H\right)=\mathcal{D}\left(G\right)$ is called a reconstruction of $G$. If every reconstruction of $G$ is isomorphic to $G$, then $G$ is said to be reconstructible. A graph that is not reconstructible is given by $G\cong K_2$ because, if $H$ is the graph consisting of two isolated vertices, then clearly $H$ is a reconstruction of $G$ but it is not isomorphic to $G$. A property $p$ defined on a class $\mathcal{F}$ of graphs is called a recognizable property if $p\left(G\right)=p\left(H\right)$ whenever $G\in \mathcal{F}$ and $H$ is a reconstruction of $G.$ A class$\mathcal{C}$ of graphs is said to be recognizable if for all graphs $G$ in $\mathcal{C}$, any reconstruction of $G$ must be in $\mathcal{C}$. A parameter$\theta =\theta \left(G\right)$ is said to be reconstructible if for all reconstructions $H$ of $G$, $\theta \left(H\right)=\theta \left(G\right)$. In other words $\theta \left(G\right)$ is reconstructible if it can be determined uniquely from the deck of $G.$ A class$\mathcal{C}$ of graphs is said to be reconstructible if every graph in $\mathcal{C}$ is reconstructible. A class $\mathcal{C}$ of graphs is said to be weakly reconstructible if for all graphs $G$ in $\mathcal{C}$, any graph in $\mathcal{C}$ that is a reconstruction of $G$ is isomorphic to $G.$

Theorem 1.3. If $G$ is a $\left(p,q\right)$-graph with $p\ge 3$, then $p$ and $q$ are reconstructible.

Proof. It is trivial to determine the number $p$, which is necessarily one greater than the order of any subgraph $G-v$. Also, $p$ is equal to the number of subgraphs $G-v.$ To determine $q$, label these subgraphs by $G_i,i=1,2,\dots p$, and suppose $G_i\cong G-v_i$, where $v_i\in V\left(G\right).$ Let $q_i$ denote the size of $G_i$. Consider an arbitrary edge $e$ of $G$, say $e=v_j{v}_k$. Then $e$ belongs to $p-2$ of the subgraphs $G_i$, namely all except $G_j$ and $G_k$.

Hence,

$$\sum _{i=1}^p{q}_i$$

counts each edge $p-2$ times. That is,

$$\sum _{i=1}^p{q}_i=\left(p-2\right)q$$

Therefore,

$$q=\frac{{\sum }_{i=1}^p{q}_i}{p-2}$$

Corollary 1.4. Given a graph $G-v$ in the deck of $G=\left(p,q\right)$, the degree of $v$ and the degrees of the neighbors of $v$ in $G$ are reconstructible.

Proof. The degree of $v$ in $G$ is simply $q-\left|E\left(G-v\right)\right|$, and this is reconstructible since $q$ is. Therefore $d$, the degree sequence in nondecreasing order of $G$, is reconstructible.

Let $d^{\prime }$ be the degree sequence of $G-v$ but with the degree of $v$ inserted in its correct position. The nonzero entries of the vector difference $d-d^{\prime }$ occur in positions corresponding to neighbors of $v$ in $G$, and their degrees can be read off from $d.$

Example 1.5. We illustrate Theorem 1.3 and Corollary 1.4 with the six subgraphs $G-v$ shown in Figure 2 of some unspecified graph $G$. From these subgraphs we determine $p$,$q$, and ${\mathit{\text{degv}}}_i$ for $i=1,2,\mathrm{...6}$. Clearly $p=6$. By calculating the $q_i,i=1,2,\mathrm{...6}$, we find that $q=9$. Thus, ${\mathit{\text{degv}}}_1={\mathit{\text{degv}}}_2=2,{\mathit{\text{degv}}}_3={\mathit{\text{degv}}}_4=3$, and ${\mathit{\text{degv}}}_5={\mathit{\text{degv}}}_6=4$.

Figure 2.

Deck of the graph $G$.

Theorem 1.6.The connectivity$\kappa \left(G\right)$of a graph$G$is reconstructible.

Proof. A graph $G$ is disconnected if and only if $\kappa \left(G\right)=0$. If $G$ is connected and let $\kappa \left(G\right)$ = $k\left(\ge 1\right)$. Then there exists a set of $k$-vertices, say $v_1,v_2,\dots ,v_k$ in $V\left(G\right)$ such that $G-\left\{v_1,v_2,\dots v_k\right\}$ is disconnected and the removal of any set of fewer than $k$-vertices from $G$ do not separable $G.$ It follows that $\kappa \left(G-v_i\right)=k-1$ for $i=1,2,\dots ,k$ and $\kappa \left(G-v\right)\ge k-1$ for $v\in V\left(G\right)=\left\{v_1,v_2,\dots ,v_k\right\}$. Hence for a connected graph $G$, $\kappa \left(G\right)-\underset{v\in V\left(G\right)}{min}\kappa \left(G-v\right)+1$. Since the R.H.S. of the above equation is known from the deck of $G$, $\kappa \left(G\right)$ is reconstructible.

Theorem 1.7.If a graph$G$is reconstructible, then the complement$\overline{G}$of$G$is reconstructible.

Proof. Let $\left\{\overline{G}-v_1,\overline{G}-v_2,\dots ,\overline{G}-v_n\right\}$ be the given deck of $\overline{G}.$ Then $\left\{\overline{\overline{G}-v_1},\overline{\overline{G}-v_1},\dots ,\overline{\overline{G}-v_n}\right\}$$=\left\{G-v_1,G-v_2,\dots ,G-v_n\right\}.$ Therefore, $\mathcal{D}\left(G\right)$ is known. Since $G$ is reconstructible, $G$ can be obtained uniquely (up to isomorphism) from $\mathcal{D}\left(G\right)$ Hence $G$ and so $\overline{G}$ is known. That is, $\overline{G}$ is reconstructible.

Theorem 1.8. Regular graphs are reconstructible.

Proof. From the deck of $G$, the degree sequence is reconstructible. Therefore, from $\mathcal{D}\left(G\right)$ it can be determined whether $G$ is regular and if it is, its degree $r$ is reconstructible.

Thus without loss of generality, we may assume that $G$ is an $r-$regular graph with $V\left(G\right)=v_1,v_2,\dots ,v_p,p\ge 3$. Take any $G-v_i$ in the deck. The only way to reconstruct a regular graph of degree $r$ from $G-v_i$ is to add a new vertex $v_i$ joining it to all the vertices of degree $d-1$ in $G-v$. Hence $G$ is uniquely reconstructible.

Theorem 1.9. For graphs of order at least $3$, connectedness is a recognizable property. In particular, if $G$ is a graph with $V\left(G\right)=v_1,v_2,\dots ,v_p,p\ge 3$, then $G$ is connected if and only if at least two of the subgraphs $G-v_i$ are connected.

Proof. Let $G$ be a connected graph. By theorem $G$ contains at least two vertices that are not cut-vertices. Let $v_1$ and $v_2$ be two vertices that are not cut-vertices. Then, clearly $G-v_1$ and $G-v_2$ are connected.

Conversely, assume that there exists vertices $v_1,v_2\in V\left(G\right)$ such that both $G-v_1$ and $G-v_2$ are connected. Thus, in $G-v_1$ and also in G, vertex $v_2$ is connected to $v_i,i\ge 3$. Moreover, $v_1$ is connected to each $v_i,i\ge 3$ in $G-v_2$ and thus in $G$. Hence every pair of vertices of $G$ are connected and so $G$ is connected.

Remark 1.10. Since connectedness is a recognizable property, it is possible to determine from the subgraphs $G-v,v\in V\left(G\right)$, whether a graph $G$ of order at least $3$ is disconnected.

Theorem 1.11. Disconnected graphs of order at least $3$ are reconstructible.

Proof. We have already noted that disconnectedness in graphs of order at least $3$ is a recognizable property. Thus, we assume without loss of generality that $G$ is a disconnected graph with $V\left(G\right)=v_1,v_2,\dots v_p,p\ge 3$. Further, let $G_i=G-v_i$ for $i=1,2,\dots p$. Hence, if $G$ contains an isolated vertex, then $G$ is reconstructible. Assume that $G$ has no isolated vertices. Among all the components of all the graphs in $\mathcal{D}\left(G\right)$, let $C$ be one with maximal number of vertices. Then $C$ must be a component of $G$. Let $v_0$ be a vertex of $C$ that is not a cut vertex. Consider all graphs in $\mathcal{D}\left(G\right)$ that have the least number of components isomorphic to $C$. Among these, let $G-v$ be the one with the largest number of components isomorphic to $C=v_0$. Then the only way to form $G$ from $G-v$ is by replacing one component $C-v_0$ by $C$.

Theorem 1.12. Separable graphs $G$ without end vertices are reconstructible.

Proof. If the given deck of $G$ contains two connectred cards and one disconnected cards, then $G$ must be connected and containing a cut vertex and so it separable. Therefore, since the degree sequence of a graph is reconstructible, the class of all separable graphs without end vertices is recognizable. Throughout this proof, blocks mean rooted blocks where roots are the cut vertices of the graph that are in the blocks. The largest end blocks of $G$ are identified as the the largest end blocks in all cards $G-v.$ Let $B$ be the one of the largest end blocks of $G$ and the unique cut vertex in $B$ is indicated in that card $G-v.$ If any non-cut vertex $w$ of $B$ is deleted from $B,$ then new rooted blocks are produced. Suppose that among the blocks so produced $B_1$ is the largest, $B_2$ the next largest (or another largest) and so on. Among all such vertex-deletions $B-w,$ some of them must produce a maximum number, say $k_1$ of $B_1$‘s. Among all those vertex-deletions $B-w$ producing $k_1$ of $B_1$‘s, some of them must produce a maximum number, say $k_2$ of $B_2$‘s, and so forth.

Now consider a card $G-u$ showing a minimum number of blocks $B,$ and a maximum number of blocks $B_1$, $B_2,$ and so forth (in that order), all with roots as marked. Then the card $G-u$ will show all blocks of $G,$ except for one $B,$ plus $k_1$$B_1$‘s, $k_2$$B_2$‘s, and so forth. Thus we can find all end blocks of $G,$ with cut vertices marked. Let $D$ be some smallest end block of $G.$ Now choose a connected card $G-v$ in which there is a smaller number of end blocks $D$ than in $G.$ Then $G-v$ must have resulted from deletion of a vertex from $D.$ Since $G$ has no end vertices, the leftovers $D-v$ is a nontrivial subgraph of $G.$ That leftovers can be identified by considering first the smallest connected subgraph, say $D^{\prime }$ of $G-v$ containing all end blocks smaller than $D.$ If $D^{\prime }$ has $\mid D\mid -1$ vertices, it is the leftovers of $D.$ Otherwise, add to $D^{\prime }$ the (unique) block which joins it to the rest of $G.$ Continue adding blocks in that way until the resulting subgraph B contains $\mid D\mid -1$ vertices. Then $G$ can be recovered by replacing $B$ by $D,$ using the same cut vertex of attachment. Hence $G$ is reconstructible.

Definition 1.13. For graphs $F$ and $G$ we denote by $s\left(F,G\right)$ the number of non-identical subgraphs $F_0$ of $G$ such that $V\left(F_0\right)\subseteq V\left(G\right),E\left(F_0\right)\subseteq E\left(G\right)$ and $F_0\cong F$.

In his thesis [1], Paul J. Kelly proved that for any two graphs $F$ and $G$ with $\left|V\left(F\right)\right|<\left|V\left(G\right)\right|,$ the number of subgraphs of $G$ isomorphic to $F$ is reconstructible from the deck of $G.$ Greenwell extended this result as follows: Let $P$ denote a graphical property. If $F$ is a subgraph of $G$ having property $P$, then the number of subgraphs of $G$ that are isomorphic to $F$ and maximal with respect to property $P$ is reconstructible from the deck of $G.$

Theorem 1.14. (Kelly’s Lemma) Let $F$ and $G$ be graphs of orders $p_1$ and $p$ respectively, where $p_1<p$. Then the number $s\left(F,G\right)$ is recognizable from the subgraphs $G-v,v\in V\left(G\right)$.

Proof. Each subgraph of $G$ isomorphic to $F$ occurs in exactly $p-p_1$ subgraphs $G-v,v\in V\left(G\right)$. Therefore,

$$\left(p-p_1\right)s\left(F,G\right)=\sum _{v\in V\left(G\right)}s\left(F,G-v\right)$$

Since the numerator of the right hand side of this equation is recognizable and $p$ and $p_1$ are known, $s\left(F,G\right)$ is recognizable. Also,

$$s\left(F,G\right)=\frac{{\sum }_{v\in V\left(G\right)}}{p-p_1}$$

3. Counting theorem

Let $P$ denote a graphical property (such as being connected, being n-connected for some $n\ge 2$ or being planar, for example).Let $G$ be a given graph, and let $F$ be a graph such that $F$ has property $P$ and $F\subset G$, that is, $s\left(F,G\right)\ge 1$. By an $\left(F,G\right)-$chain with respect to$P$,we mean a sequence of pairwise nonisomorphic subgraphs of $G$ such that each subgraph has property $P$ and

$$F\cong F_0\subset F_1\subset F_2\subset \cdots \subset F_n\subset G$$

where $V\left(F_0\right)\subseteq V\left(F_1\right)\subseteq \cdots \subseteq V\left(F_n\right)\subseteq V\left(G\right)$ and $E\left(F_0\right)\subseteq E\left(F_1\right)\subseteq \cdots \subseteq E\left(F_n\right)\subseteq E\left(G\right)$.

The chain $\left(F_0,F_1,F_2,\cdots ,F_n\right)$ is said to have length n. Two $\left(F,G\right)-$chains with respect to a property $P$ are called isomorphic if they have the same length and corresponding terms are isomorphic graphs. The rank of $F$ in $G$ (with respect to $P$) is the maximum length among all $\left(F,G\right)-$chains with respect to $P$.

Let $F$ be a subgraph of a graph $G$ such that $F$ has a graphical property $P$. Then $F$ is said to be a maximal subgraph with respect to$P$ if $V\left(F\right)\subseteq V\left(G\right)$ and $E\left(F\right)\subseteq E\left(G\right)$, and if, whenever $H$ is a subgraph of $G$ having property $P$ such that $V\left(F\right)\subseteq V\left(H\right)\subseteq V\left(G\right)$ and $E\left(F\right)\subseteq E\left(H\right)\subseteq E\left(G\right)$, it follows that $F=H$. For example, if $P_1$ is the property of being connected, then a subgraph $F$ of a graph $G$ is a maximal subgraph with respect to $P_1$ if and only if $F$ is a component of $G$. If $P_2$ denotes the property of being a block, then $F$ is a maximal subgraph with respect to $P_2$ if and only if $F$ is a block of $G$.

Let $P$ denote a graphical property and let $G$ be a given graph. If $F$ is a subgraph of $G$ having property $P$, then by ₅₄$m_P\left(F,G\right)$ we mean the number of subgraphs of $G$ that are isomorphic to $F$ and maximal with respect to property $P$. For example, if $P_2$ denotes the property of being a block and $F\cong K_3$, then for the graph $G$ of Figure 3, it follows that $s\left(F,G\right)=6$ and $m_P\left(F,G\right)=2$.

Figure 3.

The number of subgraphs with a specific property.

Theorem 1.15.(Counting Theorem). Let $G$ be a graph of order at least $3$, and let $P$ be a graphical property. Suppose that each subgraph of $G$ with property $P$ has order less than of $G$. If for each subgraph $F$ of $G$ with property $P$ and for each graph $F_0\cong F$ such that $V\left(F_0\right)\subseteq V\left(G\right)$ and $E\left(F_0\right)\subseteq E\left(G\right)$, there is a unique subgraph $H$ of $G$ that is maximal with respect to $P$ such that $V\left(F_0\right)\subseteq V\left(H\right)$ and $E\left(F_0\right)\subseteq E\left(H\right)$, then for each subgraph $F$ of $G$ having property $P$, the number $m_P\left(F,G\right)$ is recognizable.

Proof. Let $F$ be a subgraph of $G$ such that $F$ has property $P$.

By hypothesis, the order of $F$ is less than the order of $G$. Denote the rank of $F$ in $G$ by $r$.

We show that

$$m_P\left(F,G\right)={\sum }_{n=0}^r\left[\sum {\left(-1\right)}^{n}s\left(F,F_1\right)s\left(F_1,F_2\right)\cdots s\left(F_{n-1},F_n\right)s\left(F_n,G\right)\right]$$E1

where the inner sum is taken over all pairwise nonisomorphic $\left(F,G\right)-$chains $\left(F_0,F_1,\cdots F_n\right)$ of length $n$. (Note that all $\left(F,G\right)-$chains can be determined since each is contained in some $G-v$, $v\in V\left(G\right)$.)

We verify (Eq. (1)) by induction on $r$. If $r=0$, the only $\left(F,G\right)-$chain is the trivial $\left(F_0\right)$, where $F_0\cong F$. This implies that each subgraph of $G$ that is isomorphic to $F$ is, in fact, a subgraph that is maximal with respect to $P$. Thus $m_P\left(F,G\right)=s\left(F,G\right)$ and (Eq. (1)) holds in the case where $r=0$. Let $r$ be a positive integer, and assume that (Eq. (1)) is true for all subgraphs $F$ of $G$ with property $P$ and having rank less than $r$. Let $F$ be a subgraph of $G$ having property $P$ and rank $r$ in $G$. By hypothesis, for each graph $F_0\cong F$ such that $V\left(F_0\right)\subseteq V\left(G\right)$ and $E\left(F_0\right)\subseteq E\left(G\right)$, there is a unique subgraph $H$ of $G$ that is maximal with respect to $P$ such that $V\left(F_0\right)\subseteq V\left(H\right)$ and $E\left(F_0\right)\subseteq E\left(H\right)$. Thus, the number of subgraphs of $G$ isomorphic to $F$ that are subgraphs of maximal subgraphs isomorphic to $H$ is given by $s\left(F,H\right).m_P\left(H,G\right)$. Hence, if we sum these numbers over all nonisomorphic subgraphs $H$ of $G$ having property $P$, then we obtain the total number of subgraphs of $G$ isomorphic to $F$. In symbols,

$$s\left(F,G\right)=\sum s\left(F,H\right).m_P\left(H,G\right)$$

where the sum is taken over all nonisomorphic subgraphs $H$ of $G$ having property $P$. Since $s\left(F,H\right)=1$ if $H\cong F$, we have

$$m_P\left(F,G\right)=s\left(F,G\right)-\sum _{H\ne F}s\left(F,H\right).m_P\left(H,G\right)$$E2

In (Eq. (2)) it suffices to consider only those subgraphs $H$ of $G$ having property $P$ for which $s\left(F,H\right)>0$. Since any such subgraph $H$ has rank less than $r$, the inductive hypothesis can be applied to each term $m_P\left(H,G\right)$, yielding

$$m_P\left(F,G\right)=s\left(F,G\right)-\sum s\left(F,G\right)\sum _{m=0}^{\mathit{\text{rankH}}}\left[\sum {\left(-1\right)}^{m}s\left(H,H_1\right)s\left(H_1,H_2\right)\cdots s\left(H_m,G\right)\right]$$E3

where the inner sum is taken over all pairwise nonisomorphic $\left(H,G\right)$-chains $\left(H_0,H_1,\cdots ,H_m\right)$ of $H$ of $G$ having property $P$ such that $s\left(F,H\right)>0$ and $H\ne F$. Redistributing the summations in (Eq. (3)), we obtain

$$m_P\left(F,G\right)=s\left(F,G\right)-\sum \sum _{m=0}^{\mathit{\text{rankH}}}\left[\sum {\left(-1\right)}^{m}s\left(F,H\right)s\left(H,H_1\right)\cdots s\left(H_m,G\right)\right]$$

or equivalently,

$$m_P\left(F,G\right)=\sum _{n=0}^r\left[\sum {\left(-1\right)}^{m}s\left(F,H\right)s\left(H,H_1\right)\cdots s\left(H_m,G\right)\right]$$E4

where the inner sum is over all pairwise nonisomorphic $\left(F,G\right)-$chains $\left(F_0,F_1,\cdots ,F_n\right)$ of length $n$. However, this is precisely (Eq. (1)). By Theorem 1.14, the right side of (Eq. (4)) is recognizable. Thus the left hand side is recognizable.

Theorem 1.16. Let $G$ be a connected graph with two or more blocks. Then the blocks of $G$ are recognizable.

Proof. First observe that connected graphs with two or more blocks are recognizable. By Theorem 1.9 connectedness is a recognizable property. A connected graph $G$ has two or more blocks if and only if $G-v$ is disconnected for at least one vertex of $G$, that is, $v$ is a cut-vertex of $G$. Thus let $G$ be a connected graph with two or more blocks. Then each subgraph $F$ of $G$ that is a block has order less than that of $G$. Furthermore, for each $F_0\cong F$ such that $V\left(F_0\right)\subseteq V\left(G\right)$ and $E\left(F_0\right)\subseteq E\left(G\right)$, there is a unique subgraph $H$ of $G$ that is maximal with respect to the property $P_2$ of being a block (that is, a unique block $H$ of $G$) such that $V\left(F_0\right)\subseteq V\left(H\right)$ and $E\left(F_0\right)\subseteq E\left(H\right)$. Therefore by Theorem 1.15, the number $m_{P_2}\left(F,G\right)$ is the number of blocks of $G$ isomorphic to $F$.

4. Trees

Paul J. Kelly first proved that trees are reconstructible; but the proof was quite lengthy. Here we present a short proof due to Greenwell and Hemminger using the counting lemma.

A vertex $v$ of a tree $G$ is called a peripheral if it is an end-vertex of a diametrical path of $G$ that is peripheral if its eccentricity $e\left(v\right)=\mathit{\text{diamG}}$. By a branch of a central tree we mean a maximal subtree of $G$ in which the central vertex is an end vertex. A branch of a bicentral tree of $G$ is a maximal subtree of $G$ containing the central edge and in which the central edge is incident with an end vertex. A radial branch is a branch that contains a peripheral vertex of the tree. A tree is called basic if it has exactly two branches, exactly one of which is a path. The branch that is a path is called the stem of the basic tree; the other branch is called the top.

Theorem 1.17. Every tree of order at least 3 is reconstructible.

Proof. First we note that trees are recognizable. Since the order, size and connectedness of a graph $G$ can be determined from its subgraphs $G-v,v\in V\left(G\right)$, it can be recognized whether a $\left(p,q\right)$ graph $G$ is connected and $q=p-1$, that is, it can be recognized whether $G$ is a tree. Therefore, we assume that $G$ is a tree. If no vertex of $G$ has degree exceeding $2$, then $G$ is a path. Hence, paths are reconstructible. Thus, we assume that $G$ is not a path.That is, $G$ has vertices of degree $3$ or more. Then a diametrical path of such a tree $G$ necessarily has order less than $G$. From Theorem 1.14, it follows that the number of paths of various lengths in $G$ is recognizable. This implies that the diameter is a recognizable parameter.

Since the diameter of a tree equals either $2r$ or $2r-1$ according as the tree is central or bicentral, where $r$ is the radius. It further follows that the radius is recognizable and whether $G$ is central or bicentral is recognizable. We have already mentioned that the number of diametrical paths in $G$ recognizable. Now, a vertex $u$ is peripheral if and only if ${\mathit{deg}}_{G}u=1$ and $G-u$ has fewer paths of length $\mathit{\text{diamG}}$ than does $G$. Hence the number of peripheral vertices is recognizable.

A central tree $G$ with central vertex $v$ has ${\mathit{deg}}_{G}v$ branches, at least two of which are radial, while a bicentral tree has exactly two branches, both of which are radial. A tree (which is not a path) having radius $r$ is basic if and only if it contains no subgraph of Type $1,2,$or $3$, as shown in Figure 4. The central vertices are drawn as solid circles. In each case, the indicated u-v path is a diametrical path of the original tree: its length is 2r if the subtree is of Type $1$ or Type $2$ and is $2r-1$ if the subtree is of Type $3$. The length $a$ and $b$ of the indicated paths satisfy $1\le a\le r-1$ and $1\le b\le r-1$. The lengths $c$ and $d$ satisfy $1\le c\le r-2$ and $1\le d\le r-2$. If a non-basic tree contains a subtree of Type $1$, $2$ or $3$ as a proper subtree, then this is recognizable by Theorem 1.14. Thus, in order to show that all nonbasic trees are recognizable, we need only show that a non-basic tree $G$ is recognizable when $G$ itself is of Type $1,2$ or $3$.

Figure 4.

Nonbasic trees.

A tree $G$ of order $p$ is of Type $1$ if and only if it contains a path of length $2r=p-2$, one $3-$vertex, and the only subgraph $G-v$ with three components is isomorphic to $2P_r\cup K_1$. A tree $G$ of order $p$ is of Type $2$ if and only if it contains a path of length $2r=p-3$, has exactly two $3-$vertices, and in the two subgraphs $G-v$ with three components, the size of any component that is a path at most $r-2$. Finally, a tree $G$ of order $p$ is of Type $3$ if and only if it contains a path of length $2r-1=p-3$, has exactly two $3-$vertices, and each subgraph $G-v$ with three components is isomorphic to $P_{r+1}\cup P_{r-1}\cup K_1$ or in each such $G-v$, the size of any component that is a path at most $r-2$. Thus nonbasic trees of Types $1,2$ and $3$ are recognizable. Since nonbasic trees are recognizable, basic trees are also recognizable.

Claim:$1$ Basic trees are reconstructible.

Let $G$ be a central basic tree, and consider those subgraphs $G-v$ which are bicentral(basic) tree. For each such tree $G-v$, let $m_v$ denote the least distance from a vertex of degree $3$ or more in $G-v$ to a vertex incident with the central edge of $G-v$. Among all such numbers $m_v$, let $m_{v_1}$ be one of minimum value. By adding $v_1$ to $G-v_1$ and joining $v_1$ to the end-vertex of the stem of $G-v_1$, the tree $G$ is obtained. Suppose that $G$ is a bicentral basic tree. Consider all those subgraphs $G-v$ which are central(basic) trees. One of these trees, say $G-v_p$, has a vertex of degree greater than $2$ closest to the central vertex. By adding $v_p$ to $G_{v_p}$ and joining $v_p$ to the end-vertex of the stem of $G-v_p$, the tree $G$ is produced.

Claim:$2$ Nonbasic trees are reconstructible.

Let $G$ be a nonbasic tree. If $F$ is a subtree of $G$ that is maximal with respect to the property $P$ of being a basic tree having the same diameter as $G$, then we call $F$ a maximal basic subtree of $G$. Clearly, every subtree of $G$ with property $P$ has order less than that of $G$ and is a subtree of a unique maximal basic subtree of $G$. So, if such subtrees exist, by Theorem 1.14, the number of maximal basic subtrees of $G$ isomorphic to a given basic subtree $F$ of $G$ having the same diameter as $G$ is recognizable.

We now determine the radial branches of $G$. If no subtree of $G$ has property $P$, then each radial branch of $G$ is a path (of length $\mathit{\text{radG}}$) and the number of radial branches equals the number of peripheral vertices in $G$. If, on the other hand, $G$ has basic subtrees with the same diameter as that of $G$, then $G$ has radial branches that are not paths. In fact, every maximal basic subtree of $G$ gives rise to such a branch. Let $H_1,H_2,\cdots ,H_t$ be nonisomorphic subtrees of $G$ with property $P$ such that every maximal basic subtree $F$ of $G$ is isomorphic to some $H_i$, $1\le i\le t$, and such that $m_P\left(H_i,G\right)>0$ for $i=1,2,\cdots ,t$. For convenience, let $m_i=m_P\left(H_i,G\right)$. For each $i$, $1\le i\le t$, consider a maximal basic subtree $F$ of $G$ that is isomorphic to $H_i$. The tree $F$ has one radial branch $B$ that is not a path. If $G$ has $n$ peripheral vertices and $B$ contains $k_i$ peripheral vertices (of $F$ and hence of $G$), then $B$ is the top of $n-k_i$ maximal basic subtrees of $G$ isomorphic to $H_i$(namely, one for each of the $n-k_i$ stems produced from the other $n_{k_i}$ peripheral vertices). Thus, the number $m_i$ of maximal basic subtrees isomorphic to $H_i$ equals ${\mathrm{\ell }}_i\left(n-k_i\right)$, where ${\mathrm{\ell }}_i$ is the number of radial branches of $G$ isomorphic to $B$. Therefore, ${\mathrm{\ell }}_i=m_i/n-k_i$, where $m_i$, $n_i$ and $k_i$ are recognizable. The number of radial branches of $G$ that are paths equals $n-{\sum }_{i=1}^t{\mathrm{\ell }}_i{k}_i$. Since bicentral nonbasic trees have only radial branches, it follows that such trees are reconstructible. However, we still construct any nonradial branches that may exist if $G$ is a central nonbasic tree. This can be accomplished though, by observing that, in this case, the nonradial branches of $G$ are the nonradial branches of $G-v$, where.

1. $v$ is a peripheral vertex of a radial branch containing at least two peripheral vertices,or.

2. $v$ is a nonperipheral end vertex of a radial branch.

If no vertex $v$ as described in $\left(i\right)$ and $\left(\mathit{ii}\right)$ exist, then all radial branches of $G$ are paths and the nonradical branches of $G$ are the nonradical branches of $G-v$ with the exception of with the exception of one path of length $\mathit{\text{radG}}-1$, in $G-v$, where $v$ is a peripheral vertex.

We now illustrate some of the ideas involved in the proof of Theorem 1.17 by considering the subgraphs of Figure 5, where $G_i=G-v_i$ for some graph $G$ with $V\left(G\right)=v_1,v_2,\cdots ,v_{16}$.

Figure 5.

Deck of a tree.

Clearly, $G$ has order $p=16$ and, by Theorem 1.3, size $q=15$. Since $G_1$ and $G_2$, for example, are connected it follows by Theorem 1.9 that $G$ is connected. Therefore, we recognize $G$ as a tree. Hence, by Theorem 1.17 that $G$ is recognizable. Therefore, we now proceed to reconstruct $G.$.

We observe that $G$ has vertices of degree exceeding $2$ (since, for example, $G_1$ does) so that $G$ is not a path. Hence a diametrical path of $G$ has order less than that of $G$, so by determining the lengths of all paths in the subgraphs $G-v$, the maximum such length is the diameter of $G$. The maximum is $6$ (which occurs in $G_1$, for example) so that $\mathit{\text{diam}}\left(G\right)=6$. Since the diameter of a tree is either $2r$ or $2r_1$, where $r$ is the radius of the tree, depending on whether the tree is central or bicentral, it follows that $r=\mathit{\text{radG}}=3$ and that $G$ is a central tree.

In order to calculate the number $n$ of peripheral vertices of $G$, we first calculate the number of diametrical paths. This can be done with the aid of Kelly’s Lemma, in which $F\cong P_7$ and $p_1=7$. We obtain

$$s\left(P_7,G\right)=\frac{{\sum }_{v\in V\left(G\right)}s\left(P_7,G-v\right)}{16-7}=\frac{45}{9}=5$$

Thus a vertex $v_1$ of $G$ is a peripheral vertex if and only if $G-v_1$ is a tree and $G-v_1$ has fewer than five diametrical paths. The subgraphs $G_1,G_2,G_{11},$ and $G_{12}$ satisfy these criteria so that the number $n$ of peripheral vertices of $G$ is four.

We next determine whether $G$ is a basic or nonbasic (central) tree. Observe that the Type $1$ tree of Figure 6 is a subtree of at least one subgraph $G-v$ (in fact, $T$ is a subtree of all $G_i,i\ne 6$). Therefore $T$ is a proper subtree of $G$ and $G$ is nonbasic.

Figure 6.

A type $1$ subtree of $G$.

We now determine the radial branches of $G$. Since every radial branch that is not a path is the top of some maximal basic subtree of $G$ (that is, a subtree of $G$ that is maximal with respect to the property $P$ of being a basic subtree of $G$ and having diameter $6$), we begin by finding the maximal basic subtrees of $G$. By inspecting the graph, we see that only subtrees of $G$ having property $P$ are trees $H_1,H_2$ and $H_3$ shown in Figure 7. Therefore every maximal basic subtree of $G$ is isomorphic to one of $H_1,H_2$ and $H_3$.

Figure 7.

The basic subtrees of $G$ having diameter $6$.

The number $m_P\left(H_1,G\right)$ of maximal basic subtrees of $G$ isomorphic to $H_1$ can be computed with the aid of (Eq. (1)) of Theorem 1.15. By investigating the subgraphs, we see that there is only one $\left(H_1,G\right)-$chain (up to isomorphism), namely the trivial chain $\left(H_1\right)$. Thus by (Eq. (1)), $m_P\left(H_1,G\right)=\left(-1\right)s\left(H_1,G\right)$, where $s\left(H_1,G\right)$ is the number of subtrees of $G$ isomorphic to $H_1$. By using Kelly’s lemma with $p_1=9$, we have

$$s\left(H_1,G\right)=\frac{{\sum }_{v\in V\left(G\right)}s\left(H_1,G-v\right)}{16-9}=\frac{14}{7}=2.$$

Therefore there are two maximal basic subtrees of $G$ isomorphic to $H_1$.

In order to compute $m_P\left(H_2,G\right)$, we observe that, up to isomorphism, there are two $\left(H_2,G\right)-$chains, namely $\left(H_2\right)$ and $\left(H_2,H_1\right)$, where $H_1$ is shown in Figure 7. By (Eq. (1)),

$$m_P\left(H_2,G\right)={\left(-1\right)}^{0}s\left(H_2,G\right)+{\left(-1\right)}^{1}s\left(H_2,H_1\right)s\left(H_1,G\right).$$

Again using Kelly’s Lemma, we have

$$s\left(H_2,G\right)=\frac{{\sum }_{v\in V\left(G\right)}s\left(H_2,G-v\right)}{16-8}=\frac{32}{8}=4$$

One observes that $s\left(H_2,H_1\right)=2$. Also we have already seen that $s\left(H_1,G\right)=2$. So $m_P\left(H_2,G\right)=4-\left(2.2\right)=0.$ Therefore there are no maximal basic subtrees of G isomorphic to $H_2$.

In order to compute $m_P\left(H_3,G\right)$, we observe that, up to isomorphism, there are two $\left(H_3,G\right)-$chains, namely $\left(H_3\right)$ and $\left(H_3,H_1\right)$, where $H_1$ is shown in Figure 7. By (Eq. (1)),

$$m_P\left(H_3,G\right)={\left(-1\right)}^{0}s\left(H_3,G\right)+{\left(-1\right)}^{1}s\left(H_3,H_1\right)s\left(H_1,G\right).$$

Again using Kelly’s Lemma, we have

$$s\left(H_3,G\right)=\frac{{\sum }_{v\in V\left(G\right)}s\left(H_3,G-v\right)}{16-8}=\frac{16}{8}=2$$

One observes that $s\left(H_3,H_1\right)=1$ and we have already seen that $s\left(H_1,G\right)=2$. So $m_P\left(H_3,G\right)=2-\left(2.1\right)=0.$ Therefore there are no maximal basic subtrees of G isomorphic to $H_3$.

Thus $G$ has exactly two maximal basic subtrees each of which is isomorphic to $H_1$.

If $H^{\prime }$ is a maximal basic subtree of $G$, then $H^{\prime }\cong H_1$ has one non-path radial branch $B$, and $B$ is isomorphic to the graph shown in Figure 8, where $v$ corresponds to the central vertex of $G$.

Figure 8.

The unique non-path radial branch of $G$.

Since $B$ contains two of the four peripheral vertices of $G$, each radial branch isomorphic to $B$ is the top of $4-2=2$ maximal basic subtrees isomorphic to $H_1$. Thus the number $\mathrm{\ell }$ of radial branches isomorphic to $B$ equals $1$, since $m_P\left(H_1,G\right)=2$.

At this point we conclude that $G$ contains exactly one radial branch that is not a path, namely $B$. All other radial branches of $G$ are necessarily paths. Since the branch $B$ contains two of the four peripheral vertices possessed by $G$. It follows that each of the remaining two peripheral vertices corresponds to a radial branch that is a path. All radial branches of $G$ have thus been determined, as shown in Figure 9.

Figure 9.

The radial branches of $G$.

Since the tree constructed thus far has order $12$ and $G$ has order $16$, $G$ contains nonradial branches. These can be determined by noticing that $G_1$, for example, is obtained by the deletion of a peripheral vertex of $G$ belonging to the radial branch $B$. Since $B$ is isomorphic to the graph shown in Figure 9 and contains more than one peripheral vertex of $G$, the nonradial branches of $G_1$ are precisely the nonradial branches of $G$. Combining this observation with our information in Figure 9, we have constructed the tree $G$ shown in Figure 10.

Figure 10.

The tree $G$ reconstructed.

5. Diameter two or three

In 2003, S. K. Gupta [8] defined three families of simple graphs of diameter two or three and proved that the reconstruction conjecture is true if reconstruction is proved for either these three families. Already the digraph reconstruction conjecture was disproved [9]. So the proof of the reconstruction conjecture depends on any property on graphs that does not hold for digraphs. Since the diameter is one such property of graphs, graph theorists thought that the final proof of the reconstruction conjecture may hold in this line of direction. Gupta’s reduction of the reconstruction conjecture is presented next.

Gupta defined three disjoint families of simple graphs, namely ${\mathcal{F}}_1$,${\mathcal{F}}_2$ and ${\mathcal{F}}_3$ such that the reconstruction conjecture is true if it true for the families ${\mathcal{F}}_1$,${\mathcal{F}}_2$ and ${\mathcal{F}}_3$. These families are quite restrictive in that each has diameter two or three. First of all, it is proved that these families ${\mathcal{F}}_1$,${\mathcal{F}}_2$ and ${\mathcal{F}}_3$ are recognizable by showing that graphs of diameter two are recognizable. The reconstruction conjecture is thus reduced to showing weak reconstructibility for the three families.

Theorem 1.18. If a graph $G$ has diameter greater than three then the diameter of $\overline{G}$ is less than three.

Proof. Let $G$ be a connected with diameter greater than $3$.

Then there exists $u,v\in V\left(G\right)$ such that $d\left(u,v\right)>3$. Clearly the graph $\overline{G}$ will contain the edge $\mathit{uv}$. In $\overline{G}$ any vertex different from $u$ and $v$ is adjacent to $u$ or to $v$ or to both since there is no path of length $3$ connecting $u$ and $v$ in $G$.

Let $x$ and $y$ be any two vertices different from $u$ and $v$. If they have $u$ or $v$ as a common neighbor in $\overline{G}$, then $\mathit{xuy}$ or $\mathit{xvy}$ is a path connecting them in $\overline{G}$. Otherwise, they must be adjacent in $\overline{G}$ since neighbors of $u$ and neighbors of $v$ are not adjacent in $G.$

Now define.

1. ${\mathcal{C}}_1:$ class of all graphs $H$ such that $\mathit{\text{diam}}\left(H\right)=\mathit{\text{diam}}\left(\overline{H}\right)=2.$

2. ${\mathcal{C}}_2:$ class of all graphs $H$ such that $\mathit{\text{diam}}\left(H\right)=2$ and $\mathit{\text{diam}}\left(\overline{H}\right)>2.$

3. ${\mathcal{C}}_3:$ class of all graphs $H$ such that $\mathit{\text{diam}}\left(H\right)=\mathit{\text{diam}}\left(\overline{H}\right)=3.$

For $i\in \left[0,n-2\right],$$\mathit{pv}\left(H,i\right)$ is the number of pairs of non-adjacent vertices of $H$ such that, for each pair, there are exactly $i$ paths of length two between the two vertices, and $\mathit{pav}\left(H,i\right)$ is the number of pairs of adjacent vertices of $H$ such that, for each pair, there are exactly $i$ paths of length two between the two vertices.

Theorem 1.19. If $\mathit{pv}\left(H,n-2\right)>0$ or $\mathit{pav}\left(H,n-2\right)>0$ then $\overline{H}$ is disconnected.

Proof. If $\mathit{pv}\left(H,n-2\right)>0$ or $\mathit{pav}\left(H,n-2\right)>0,$ then $H$ must contain at least one pair of vertices, say $\left(u,v\right),$ such that there are $n-2$ paths of length two between $u$ and $v,$ which means vertices $u$ and $v$ are adjacent to all other remaining $n-2$ vertices of $H.$ Hence, in $\overline{H},$ no vertices other than $u$ and $v$ are adjacent to them. Therefore, in $\overline{H},$ either $u$ and $v$ are isolated vertices or they together form a component isomorphic to $K_2.$ Thus, $\overline{H}$ is disconnected.

Theorem 1.20.

$$\left(a\right)\sum _{i=1}^n\mathit{pv}\left(H_i,j\right)=\left(j+1\right)\mathit{pv}\left(H,j+1\right)+\left(n-\left(j+2\right)\right)\mathit{pv}\left(H,j\right)\forall j\in \left[0,n-3\right]$$

$$\left(b\right)\sum _{i=1}^n\mathit{pav}\left(H_i,j\right)=\left(j+1\right)\mathit{pav}\left(H,j+1\right)+\left(n-\left(j+2\right)\right)\mathit{pav}\left(H,j\right)\forall j\in \left[0,n-3\right]$$

Proof. (a) Let $\left(u,v\right)$ be a pair of vertices in the graph $H$ such that $d\left(u,v\right)=2$ and let there be exactly $k$ paths of length two $\left({\mathit{uv}}_{1}v,{\mathit{uv}}_{2}v,\dots ,{\mathit{uv}}_{k}v\right)$ between $u$ and $v$. Then, both in $H-u$ and $H-v,$ the pair $\left(u,v\right)$ will not appear at all. In each of the $k$ cards $H-v_i,$ where $i=1,2,\dots ,k,$ this pair $\left(u,v\right)$ appears as having $k-1$ paths of length two. In the remaining $n-k$ cards, this pair will appear as having $k$ paths of length two.

(b) Proof is similar to Part(a) but taking $\left(u,v\right)$ as a pair of adjacent vertices.

Theorem 1.21.Parameters$\mathit{pv}\left(H,i\right)$and$\mathit{pav}\left(H,i\right)$are reconstructible for all$i\in \left[0,n-2\right].$

Proof. First we prove that the parameters $\mathit{pv}\left(H,i\right)$ are reconstructible and that of $\mathit{pav}\left(H,i\right)$ follows similarly.

From the given deck of $H$, the left hand side of Theorem 1.20(a) is known for $j\in \left[0,n-3\right]$. Thus, from Theorem 1.20(a), we have $n-2$ independent linear equations of $n-1$ parameters $\mathit{pv}\left(H,0\right),\mathit{pv}\left(H,1\right),\cdots ,\mathit{pv}\left(H,n-3\right)$ and $\mathit{pv}\left(H,n-2\right).$

Case 1. Suppose $\mathit{pv}\left(H,n-2\right)>0.$

Now, by Theorem 1.19, $\overline{H}$ is disconnected. So $\overline{H}$ and hence $H$ is reconstructible. Then each parameter $\mathit{pv}\left(H,i\right)$ (where $i\in \left[0,n-2\right]$) is clearly reconstructible.

Case 2: Suppose $\mathit{pv}\left(H,n-2\right)=0.$

In this case, we have an additional linearly independent equation $\mathit{pv}\left(H,n-2\right)=0$ apart from the $n-1$ equations stated in Theorem 1.20(a). Now we have $n-1$ linearly independent equations with $n-1$ unknowns namely $\mathit{pv}\left(H,0\right),\mathit{pv}\left(H,1\right),\cdots ,\mathit{pv}\left(H,n-3\right)$ and $\mathit{pv}\left(H,n-2\right).$ The unique solution set of these equations will provide the values of the parameters $\mathit{pv}\left(H,0\right),\mathit{pv}\left(H,1\right),\cdots ,\mathit{pv}\left(H,n-2\right).$

Theorem 1.22.Graphs of diameter two are recognizable.

Proof. Graphs of diameter one are precisely complete graphs and so they are recognizable. If diam$\left(H\right)\ne 1$ and $\mathit{pv}\left(H,0\right)=$ 0, then diam$\left(H\right)=$ 2 since $\mathit{pv}\left(H,i\right)$ (where $i\in \left[0,n-2\right]$) is the number of pairs of non-adjacent vertices of $H$ such that, for each pair, there are exactly $i$ paths of length two between the two vertices. If $\mathit{pv}\left(H,0\right)>$ 0, then diam$\left(H\right)>$2.

The number of pairs of vertices of $H$ such that distance between vertices of each pair is greater than two (or $\mathit{pv}\left(H,0\right)$) is reconstructible.

Theorem 1.23. Families ${\mathcal{C}}_1,{\mathcal{C}}_2$ and ${\mathcal{C}}_3$ are recognizable.

Proof. Given the deck of some graph $H$, $\mathcal{H}=\left\{H_i|i\in \left[1,n\right]\right\}$, we can get the deck of $\overline{H}$, ${\mathcal{H}}^{\prime }=\left\{\overline{H_i}|i\in \left[1,n\right]\right\}$. We can recognize whether $\mathit{\text{diam}}\left(H\right)=1$ or not (as complete graphs are recognizable). If $\mathit{\text{diam}}\left(H\right)\ne 1$ and $\mathit{pv}\left(H,0\right)=0$, then $\mathit{\text{diam}}\left(H\right)=2$. If $\mathit{pv}\left(H,0\right)>0$, then $\mathit{\text{diam}}\left(H\right)>2$. So we can recognize both $H$ and $\overline{H}$ whether they have diameter equal to one or two or greater than two. So, ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$ are recognizable. We have, if $\mathit{\text{diam}}\left(H\right)>2$ and $\mathit{\text{diam}}\left(\overline{H}\right)>2$ then $\mathit{\text{diam}}\left(H\right)=3$ and $\mathit{\text{diam}}\left(\overline{H}\right)=3$. Also, $G\in {\mathcal{C}}_3$ if and only if $\mathit{\text{diam}}\left(H\right)>2$ and $\mathit{\text{diam}}\left(\overline{H}\right)>2$. Hence ${\mathcal{C}}_3$ is also recognizable.

The next well known result is useful while proving the reduction of the Reconstruction Conjecture.

Theorem 1.24 ([10]). If a graph $H$ has diameter greater than three then the diameter of $\overline{H}$ is less than three.

Theorem 1.25 ([11]). If a graph $H$ has radius greater than three then the radius of $\overline{H}$ is less than three.

Theorem 1.26 (Gupta et al. [8]). The Reconstruction Conjecture is true if and only if all graphs $H$ with $\mathit{\text{diam}}\left(H\right)$$=2$ and all graphs $H$ with $\mathit{\text{diam}}\left(H\right)=\mathit{\text{diam}}\left(\overline{H}\right)=3$ are reconstructible.

Proof. The necessity is obvious. For sufficiency, let $H$ be a graph. If $H$ is disconnected, then it is reconstructible. So, we can take that $H$ is connected. If $\mathit{\text{diam}}\left(H\right)=2$ or $\mathit{\text{diam}}\left(H\right)=\mathit{\text{diam}}\left(\overline{H}\right)=3$, then $H$ is reconstructible by hypothesis. Hence we may assume that $\mathit{\text{diam}}\left(H\right)=1$ or, by Theorem 1.24, $\mathit{\text{diam}}\left(\overline{H}\right)\le 2$. If $\mathit{\text{diam}}\left(H\right)=1$ or $\mathit{\text{diam}}\left(\overline{H}\right)=1$, then $H$ is reconstructible (because graphs with diameter one are precisely complete graphs). Hence we assume $\mathit{\text{diam}}\left(\overline{H}\right)=2$. Now $\overline{H}$ is reconstructible by assumption. Hence $H$ is reconstructible by Theorem 1.7.

Theorem 1.27.Graphs on$n$vertices having an$\left(n-1\right)$-vertex are reconstructible.

Proof. Since the degree sequence of $H$ is reconstructible, we can recognizable whether the graph has a vertex of degree $n-1$ or not. Therefore the claim of under consideration is recognizable, weakly reconstructible. In a card $H-v$, where ${\mathit{deg}}_{H}v$ = $n-1$, annexing a new vertex to $H-v$ and joining it all the vertices of $H-v$; the graph $H$ in this way is unique. Hence $H$ is reconstructible.

Lemma 1.28.Separable graphs$H$with diam$\left(H\right)=$2 are reconstructible.

Proof. We know that, graphs $G$ with diam$\left(H\right)=$2 are recognizable. A connected graph is separable if and only if one of its cards is disconnected. Now $H$ has no non-end block, as otherwise $H$ has diameter greater than 2. So all the blocks of $H$ are end-blocks. Hence $H$ has only one cut vertex, say $v$. Since diam$\left(H\right)=$2, $v$ must be adjacent to all other vertices of $H$. Hence $H$ is reconstructible.

Yang Yongzhi [2] proved the following reduction of the Reconstruction Conjecture in 1988. Yongzhi achieved this significant reduction of the RC by proving the reconstructibility of a new class of graphs called $P$-graphs. Yongzhi observed that reconstructibility of P-graphs turns out to be of great use while shuttling between a graph and its complement in order to reconstruct it.

Figure 11.

A P-graph on 9 vertices.

Definition 1.29.A graph$G$with$p$vertices is a$P$-graph, if.

1. there exists only two blocks in$G$and one of them is an edge (denote it by$\mathit{rx}$with$d\left(x\right)=1),$and

2. there exists a vertex$u\ne r,d\left(u\right)=p-2$ (Figure 11).

Lemma 1.30.$P$-graphs are recognizable.

Proof. Since the degree sequence and the number of cut vertices are reconstructible, recognizability of (i) of Definition 1.31 follows immediately. Existence of $u$ as in (ii) of Definition 1.31 is guaranteed by the existence of a connected card obtained by deleting a $p-2$ vertex in the given deck of $G.$.

Every graph must be contained in one of the following disjoint classes of graphs: disconnected graphs (which are reconstructible); separable graphs without end vertices (which are reconstructible); separable graphs with end vertices; and $2$-connected graphs. Yongzhi [12] further divided the class of separable graphs with end vertices into $P$-graphs and other than $P$-graphs, and proved that the former class of graphs is reconstructible if all $2$-connected graphs are reconstructible. We omit the proof as it is very lengthy.

Theorem 1.31. P-graphs are reconstructible if all 2-connected graphs are reconstructible.

Theorem 1.32. Every connected graph is reconstructible if and only if every $2$-connected graph is reconstructible.

Proof. The necessity is obvious. For proving the sufficiency part, assume that all 2-connected graphs are reconstructible. Let $G$ be a separable graph on $p$ ($\ge 12$) vertices. If $G$ has no end vertex then $G$ is reconstructible (by Theorem 1.12).

$$\begin{array}{c}\text{Thus},\text{we}\mathrm{can}\text{assume that}G\mathrm{has}\text{an}\mathrm{end}\text{vertex and}\mathrm{a}\left(p-2\right)\\ -\text{vertex}\left(\text{because of Theorems}1.12\text{and}1.7\text{and the hypothesis}\right).\end{array}$$E5

We have two subcases.

Case 1. The graph $G$ has at least two end vertices.

$$\mathrm{Now}\overline{G}\mathrm{has}\mathrm{at}\text{least}\mathrm{two}\left(p-2\right)-\text{vertices}.$$E6

Let $u_1$ and $u_2$ be two $\left(p-2\right)$-vertices in $\overline{G}$. By (Eq. (6)), $\overline{G}$ has at most two end vertices and (Eq. (5)) now gives that $\overline{G}$ has either one or two end vertices.

Case 1.1. The graph $\overline{G}$ has exactly one end vertex, say $y.$.

Now $\overline{G}$ is a $P$-graph (as in (i) and (ii) below) and hence $G$ is reconstructible by Theorem 1.31.

(i) If $y$ is not adjacent to $u_i,i=1,2,$ then in $\overline{G}-y$, $u_1$ and $u_2$ are $\left(p-2\right)$-vertices and hence $\overline{G}-y$ is a block as $\overline{G}-y$ has only p?1 vertices. Hence $\overline{G}$ is a $P$-graph.

(ii) If $y$ is adjacent to $u_1$ (say), then in $\overline{G}-y$, $u_2$ is adjacent to all the vertices hence no vertex other than $u_2$ can be a cut vertex of $\overline{G}-y$. Also if $u_2$ were a cut vertex of $\overline{G}-y$, then $u_1$ and all its $p-3$ neighbors in $\overline{G}-y$ are confined to a single block with $p-2$ vertices and the only other vertex of $\overline{G}-y$ must be an end vertex adjacent to $u_2$. Thus $\overline{G}$ has two end vertices, leading to a contradiction. Hence $\overline{G}-y$ has no cut vertex and $\overline{G}$ is a $P$-graph.

Case 1.2. The graph $\overline{G}$ has exactly two endvertices.

Now the bases of the two endvertices in $\overline{G}$ are different (otherwise $\overline{G}$ has at most one $\left(p-2\right)$-vertices, contradicting (Eq. (6))). No vertex other than the bases of the endvertices can have degree $p-2.$ Hence $\overline{G}$ has at most two $\left(p-2\right)$-vertices and (Eq. (6)) now gives that has exactly two $\left(p-2\right)$-vertices, which are the bases of the endvertices. In this case $\overline{G}$ is clearly recognizable from its degree sequence and is reconstructible by augmenting an end vertex-deleted card $\overline{G}-y$ (by adding a vertex to $\overline{G}-y$ and joining it to a $\left(p-3\right)$-vertex).

Case 2. The graph $G$ has exactly one end vertex, say y.

If $G$ has more than one $\left(p-2\right)$-vertex, then $G$ is a P-graph and hence is reconstructible by Theorem 1.31. Hence let $G$ have exactly one $\left(p-2\right)$-vertex, say $w$

Case 2.1. The vertices $w$ and $y$ are nonadjacent in $G$.

Now we can assume that $w$ is a cut vertex of $G$ as otherwise $G$ is a $P$-graph and hence is reconstructible. So $w$ and $q$ (the base of $y$) are the only cut vertices of $G$. Hence $G$ is the union of three subgraphs $B_{\mathit{wq}}$ (the non-end block containing $w$ and $q$), $F_w$ (the union of end-blocks containing $w$) and the end-block $B_y$ ($K_2$) containing $y.$

If $\mathit{deg}q=p-3$ then $F_w\cong K_3$ (because $G$ has only one end vertex). Consider a 2-vertex deleted card $G-z$ with exactly two end vertices (the deleted 2-vertex cannot be from $B_{\mathit{wq}}$ as every 2-vertex in $B_{\mathit{wq}}$ is adjacent to $w$ and $q$ so that no additional end vertex is created). Such a $G-z$ will have an automorphism that interchanges the two end vertices, interchanges the two bases and fixes all other vertices. Hence all augmentations of $G-z$ by introducing a 2-vertex so that the resulting graph has only one end vertex and only one end-block isomorphic to $K_3$ are isomorphic.

If $\mathit{deg}q\ne p-3$ then $\mathit{deg}q<p-3$ (because $\mid \mathit{Fw}\mid \ge 3$). Now in the cards $G-v$ that are connected and have at least one end vertex (cards for which the deleted vertex is not one of $w,y$ and $q$), the vertices $w,y$ and $q$ are identifiable as the only cut vertex of degree $p-3,$ the only end vertex nonadjacent with $w$ and the base of $y$ respectively. Among these cards $G-v$, if we choose one, say $G_1$ such that.

1. $w$ and $q$ are in the same block, and.

2. the block containing $w$ and $q$ has maximum number of vertices,

then the non-end block of $G_1$ is $B_{\mathit{wq}}$. Hence $B_{\mathit{wq}}$ is known with $w$ and $q$ labeled.

The only end vertex-deleted card in the deck is $G-y$ and its only cut vertex is $w.$ Since $B_{\mathit{wq}}$ is known with $w$ and $q$ labeled, there is an isomorphism $\alpha$ from $B_{\mathit{wq}}$ on to a block of $G-y$ such that $\alpha \left(w\right)=w$. The graph $G_{\alpha }$ obtained from $G-y$ by adding a vertex and joining it only with $\alpha \left(q\right)$ is a candidate for $G$. If $\beta$ is another such isomorphism and $G_{\beta }$ is the corresponding augmented graph, then $G_{\alpha }\cong G_{\beta }$ under the mapping $\psi$ where

$$\begin{array}{l}\psi =\left\{\begin{array}{ll}{\mathit{\beta \alpha }}^{-1}& \mathrm{on}\text{the\hspace{0.17em}vertices\hspace{0.17em}of}\alpha \left(B_{\mathit{wq}}\right)\\ {\mathit{\alpha \beta }}^{-1}& \mathrm{on}\text{the\hspace{0.17em}vertices\hspace{0.17em}of}\beta \left(B_{\mathit{wq}}\right)\\ \mathit{\text{identity}}& \mathrm{on}\mathrm{all}\text{other\hspace{0.17em}vertices}\end{array}\right.\\ \text{when}\alpha \left(B_{\mathit{wq}}\right)\text{and}\beta \left(B_{\mathit{wq}}\right)\mathrm{are}\text{different blocks of}G-y\text{and}\\ \psi =\left\{\begin{array}{ll}{\mathit{\beta \alpha }}^{-1}& \mathrm{on}\text{the\hspace{0.17em}vertices\hspace{0.17em}of}\alpha \left(B_{\mathit{wq}}\right)\\ \mathit{\text{identity}}& \mathrm{on}\mathrm{all}\text{other\hspace{0.17em}vertices}\end{array}\right.\\ \text{when}\alpha \left(B_{\mathit{wq}}\right)\text{and}\beta \left(B_{\mathit{wq}}\right)\mathrm{are}\text{different blocks of}G-y.\end{array}$$

Hence $G$ is known up to isomorphism.

Case 2.2. The vertices $w$ and $y$ are adjacent in $G$.

Now in $\overline{G}$, $w$ is the only end vertex and $y$ is the only $\left(p-2\right)$-vertex and they are not adjacent. Hence $\overline{G}$ is reconstructible as in Case 2.1. This completes the proof.

“Reconstruction Conjecture for digraphs” is already disproved by Stockmeyer [9]. So a proof for the Reconstruction Conjecture will depend on some property for graphs which does not extend to digraphs. Such properties are called significant properties (from the reconstruction angle) by Stockmeyer. One such property which arises out of distance in complement is given by Theorems 1.7 and 1.24. So far, in digraphs, there is no definition of complement and diameter such that Theorem 1.7 and 1.24 are simultaneously true. So reductions of the Reconstruction Conjecture obtained using the above theorems apply only for graphs and deserve attention. One reduction was proved in the last chapter (Theorem 1.26) by Gupta et al. [8] using Theorems 1.7 and 1.24. Reconstructibility of the subfamilies of 2-connected graphs in the families ${\mathrm{ℱ}}_1,{\mathrm{ℱ}}_2$ and ${\mathrm{ℱ}}_3$ are sufficient for the truth of the Reconstruction Conjecture.

Theorem 1.33 ([13]).All 2-connected graphs are reconstructible if and only if all 2-connected graphs$G$such that diam$\left(G\right)=$2 or diam$\left(G\right)$= diam$\left(\overline{G}\right)=$3 are reconstructible.

Proof. The necessity is obvious. For sufficiency, let $G$ be a 2-connected graph. Since graphs of diameter one are precisely complete graphs, this, together with hypothesis, leaves us to reconstruct only 2-connected graphs $G$ of types (a) and (b) below.

$\left(a\right)$ diam$\left(G\right)=$3 but diam$\left(\overline{G}\right)$ is different from 3.

If diam$\left(\overline{G}\right)>$3, then by Theorem 1.24, diam$\left(G\right)<$3, giving a contradiction. Hence diam$\left(\overline{G}\right)=2.$ Hence $\overline{G}$ is reconstructible, by Lemma 1.28 if it is separable and by hypothesis otherwise.

$\left(b\right)$ diam$\left(G\right)>$3.

Now, by Theorem 1.24, diam$\left(\overline{G}\right)<$3 and so diam$\left(\overline{G}\right)=2,$ since $G$ is connected. Therefore $\overline{G}$ and hence $G$ is reconstructible by hypothesis.

Theorem 1.34. All graphs are reconstructible if and only if all 2-connected graphs $G$ such that diam$\left(G\right)=$2 or diam$\left(G\right)$ = diam$\left(\overline{G}\right)$ = 3 are reconstructible.

Proof. Follows by Theorems 1.32 and 1.33.

6. Radius two

Theorem 1.35.If$G$is connected and rad$\left(G\right)\ge 3$, then rad$\left(\overline{G}\right)\le 2$and$\overline{G}$has no endvertices.

Proof. Let $G$ be a connected graph with rad$\left(G\right)\ge 3$. Then rad$\left(\overline{G}\right)\le 2$. If possible, let $\overline{G}$ have endvertices. Then $G$ has an $\left(n-2\right)$-vertex say $v$. Hence $v$ is adjacent to all but one vertex, say $v^{\prime }$ of $G$. Hence $v^{\prime }$ is adjacent to at least one neighbor of $v$ in $G$ (as $G$ is connected). Hence $d\left(v,w\right)\le 2,\forall w\in V\left(G\right)$. Hence rad$\left(G\right)\le 2$, giving a contradiction. This completes the proof.

Theorem 1.36. All 2-connected graphs are reconstructible if and only if all 2-connected graphs $G$ with rad$\left(G\right)$ = 2 are reconstructible.

Proof. The necessity is obvious. For sufficiency, let $G$ be any 2-connected graph. It is enough to show that $G$ or $\overline{G}$ is reconstructible. If rad$\left(G\right)=1$, then $G$ has a vertex adjacent to all other vertices and hence $G$ is reconstructible. If rad$\left(G\right)=2$, then $G$ is reconstructible by hypothesis.

Now let rad$\left(G\right)\ge 3$. Then rad$\left(\overline{G}\right)\le 2$ and $\overline{G}$ has no endvertices by Theorem 1.35. If rad$\left(\overline{G}\right)=1$, then $\overline{G}$ is reconstructible as it has a vertex adjacent to all other vertices. When rad$\left(\overline{G}\right)=2$, $\overline{G}$ is disconnected, separable without end vertices or 2-connected. Therefore $\overline{G}$ is reconstructible by Theorem 1.11, Theorem 1.28 or the hypothesis.

Theorem 1.37 ([13]). All graphs are reconstructible if and only if all 2-connected graphs $G$ such that rad$\left(G\right)=2$ are reconstructible.

Proof. By Theorem 1.32, we have all graphs are reconstructible if and only if all 2-connected graphs are reconstructible. We also know that all 2-connected graphs are reconstructible if and only if all 2-connected graphs $G$ such that rad$\left(G\right)$ = 2.

As 2-connected graphs are recognizable, the families of 2-connected graphs in the hypothesis of Theorems 1.34 and 1.37 are recognizable. Thus, to settle the Reconstruction Conjecture, it is enough to prove that neither of these two families contains a pair of non-isomorphic graphs having the same deck. However, radius of a graph is not yet proved to be reconstructible.

Many classes of blocks which are cartesian, lexicographic or strong products of graphs have been shown to be weakly reconstructible [6, 7]. Several other families of graphs already proved to be reconstructible contain 2-connected graphs. As there are a number of results on the structure of special classes of graphs of diameter 2, they may lead to the reconstruction of more classes of graphs and further narrow down the classes of graphs to be reconstructed to prove the Reconstruction Conjecture. These narrowed down classes must contain counterexamples to the Reconstruction Conjecture if at all there exists one.