**Background**

Let $G$ be a finite graph on $v$ vertices. The *deck*, $D(G)$, of $G$ is the multi-set of vertex-deleted subgraphs of $G$. The Graph Reconstruction Conjecture asserts that for finite graphs $G$ and $H$ on $v\ge 3$ vertices, if $D(G)=D(H)$, then $G\cong H$.

**Motivation**

Consider a graph $G$ and chose a vertex labeling $\phi:[v]\to V(G)$ where $[v]=\{1,\dots,v\}$ and $V(G)$ is the vertex set of $G$. We denote the $i$-th vertex-deleted subgraph of $G$ by $G_i$ which corresponds to deleting the $i$-th vertex and all incident edges and $D(G)=\{G_1,\dots, G_v\}$.

For each $G_i$, chose a map $\psi_i:[v]\setminus\{i\}\to V(G_i)$. From this vertex labeling we may construct an adjacency matrix in which the $(r,c)$-th entry of the matrix is $1$ if edge $\{r,c\}$ is present and $0$ otherwise. The dimension of this matrix is $(v-1)\times (v-1)$. We can extend this matrix to a $v\times v$ matrix by inserting a zero row and column in the $i$-th row/column and we will denote this matrix by $A_i$. The interpretation of this matrix is that it is the adjacency matrix for $G_i$ with a disjoint point appended to the graph.

We now introduce the following theorem:

* Theorem* Consider the set of adjacency matrices for the vertex-deleted subgraphs of a graph $G$ (where the vertex labeling is fixed) and the matrices are extended by a point as explained above. Denote each matrix as $A_i$. Then,

$\frac{1}{v-2}\displaystyle\sum_{i=1}^{v} A_i = A$

where $A$ is the adjacency matrix of $G$.

Consider a function $\Gamma:Sym(v)^v \to \mathbb{R}^{v\times v}$ where $Sym(v)$ is the group of $v\times v$ permutations matrices. The function has the following form:

$\Gamma_D(S)= \frac{1}{v-2} \displaystyle\sum_{i=1}^{v} S_i A_i S_i^T$

where $S=(S_1,\dots,S_v)\in Sym(v)^v$ and $D$ denotes the sum is taken over adjacency matrix constructed via the method describe above from deck $D$.

For arbitrary choice of $\psi_i$ and $S$, it is not necessarily the case that $\Gamma_D(S)$ is an adjacency matrix (i.e. binary, symmetric, trace of zero). However, if it is, it seems that $\psi_i$ permuted by $S_i$ would define a coherent reconstruction of the graph.

**Conclusion**

Overall, the aim of this function $\Gamma$ is to provide an algebraic framework for graph reconstruction. In other words, it seems that if $\Gamma_D(S)$ and $\Gamma_D(R)$ are adjacency matrix and $\Gamma_D(S) = \Gamma_D(R)$ then $R$ is necessarily a permutation of $S$, hence the underlying reconstructed graphs are isomorphic.

**Note**

I apologize for the length on strange formulation of these ideas. The process is a bit difficult to describe. Please feel free to comment with suggestions and questions to improve clarity.