Confusion with the reconstruction conjecture?

192 Views Asked by At

After reading about the reconstruction conjecture for graphs, I came up with what I thought was a proof by contradiction. Consider the class $T$ of (isomorphism classes of) finite graphs, and the function $D$ such that $D(A)$ is the deck of $A$. The Reconstruction conjecture states $D(G)=D(H) \iff G=H$. Assume this is true. Then $D(D(G))=D(D(H)) \iff G=H$. Continuing gives that the null graph is equal to the null graph $\iff G=H$.

2

There are 2 best solutions below

0
On

The idea is nice, but the reconstruction conjecture excludes some very small graphs. Both graphs on 2 vertices have the same deck.

4
On

I'm no expert in graph theory, but I don't see what the type of $D(D(G))$ is. I think the problem comes from defining $D$ on decks of graphs, rather than just graphs. Also, the conjecture isn't true for graphs with two vertices anyway, so the induction should stop before that.