MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Why is the edge reconstruction conjecture stated with the deck defined as the multi set of graphs formed by deleting one edge? Can someone give an example of two graphs such that the edge deleted subgraph set is the same but the multi set is different?

share|cite|improve this question
Your vertex example has a problem: $3n$ vertices versus $3n-3$ vertices. – Brendan McKay Jul 24 '14 at 13:36
Thank you, i realised it doesn't work (even if i hadn't made the mistake of writ in n-2 instead of n-1). It only gives subgraphs of n copies of $K_{1,2} \subset$ subgraphs of (n-1 copies of $K_{1,2} \cup K_1 \cup K_2$), the reverse isn't true. – Thinniyam Srinivasan Ramanatha Jul 25 '14 at 6:57
@DagOskarMadsen But the set reconstruction is stated only for vertex right? What about edge reconstruction? Is there a set version for that as well? – Thinniyam Srinivasan Ramanatha Aug 13 '14 at 8:09
Sorry, you are right. I will delete my comment. – Dag Oskar Madsen Aug 13 '14 at 8:54

Harary conjectured that the set of vertex deleted subgraphs is unique up to isomorphism. (On the reconstruction of a graph from a collection of subgraphs. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52.)

If you could find an example, you would have proven Haray's strong reconstruction conjecture false. This is because if the vertex reconstruction conjecture is true, then the edge reconstruction conjecture is true, thus the same would hold for the set versions.

share|cite|improve this answer
I know the result that deck is reconstructible from edge deck, but is the same true for the sets? – Thinniyam Srinivasan Ramanatha Dec 18 '14 at 6:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.