0
$\begingroup$

Suppose we have a complete graph invariant $I$ i.e. for any two graphs $G$ and $H$ we have $ I(G)=I(H) \iff G \cong H $. Suppose now that the invariant $I$ is reconstructible from the desk of $G.$ May I deduce now that the Reconstruction Conjecture is true?

For example, consider a graph $G$ and let $G_1, G_2,\ldots, G_N$ be the set of representatives of all clases isomorphic subgraphs of $G$. Let $I(G)=[k_1(G), k_2(G), \ldots, k_N(G)]$ where $k_i(G)$ is number of subgraphs of $G$ which are isomorphic to the subgraph $G_i.$ We have that $I(G)$ is a complete invariant and each $k_i(G)$ is reconstructible (it follows from Kelly formula) then the Reconstruction Conjecture is true.

Where is my mistake?

$\endgroup$
3
  • 2
    $\begingroup$ Your mistake is that Kelly's lemma only gives counts for subgraphs with fewer vertices than $G$ and nobody can prove that is a complete invariant. $\endgroup$ Feb 9, 2017 at 23:16
  • $\begingroup$ Thank you. Sorry for stupid questions but 2 points are still uncler for me. 1. All graphs $G_i$ of course have fewer vertices than $G$ so Kelli's lema works. 2. Does $I(G)$ not complete invariant? There is a counterexample? $\endgroup$
    – Leox
    Feb 10, 2017 at 7:40
  • $\begingroup$ Nobody knows if $I(G)$ is a complete invariant. Solving that question is basically the same as solving the reconstruction conjecture. $\endgroup$ Feb 10, 2017 at 7:45

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.