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

Let $G$ be a simple graph. Let $E^-(G)$ denote the set of (isomorphism classes) of subgraphs of $G$ that can be obtained by deleting a single edge of $G$. Similarly, let $E^+(G)$ be the set of (isomorphism classes) of simple graphs that can be obtained by adding a single edge to $G$. Is $G$ uniquely determined by $E^-(G)$ and $E^+(G)$? Thank you in advance!

Are there any other examples besides the two graphs on 4 vertices?

share|cite|improve this question
Do you mean to have the data as sets or as multisets? Are the edge deleted subgraphs given with multiplicity? – Gjergji Zaimi Nov 23 '13 at 7:22

Let $V=\{a,b,c,d\}$, $E_1=\{(a,b),(a,c),(a,d)\}$, $E_2=\{a,b),(a,c),(b,c)\}$, $G_1=(V,E_1)$, and $G_2=(V,E_2)$. Then $E^-(G_1)=E^-(G_2)$ and $E^+(G_1)=E^+(G_2)$ although $G_1$ and $G_2$ are not isomorphic.

share|cite|improve this answer
It couls very wel be the only example... – Jérôme JEAN-CHARLES Feb 22 '14 at 0:34

Except for finitely many cases, $G$ can be reconstructed from the largest of $E^-(G)$ and $E+(G)$. Note that you have the edge-decks of both $G$ and its complement.

Lovász proved that $G$ is edge-reconstructible if it has more edges than its complement. That covers all cases except when $G$ has exactly $n(n-1)/4$ edges.

Müller proved that graphs with more than $n(\log_2(n)-1)$ edges are edge-reconstructible. That finishes it for all $n\ge 12$. The cases $n=10,11$ don't happen, as $n(n-1)/4$ is not an integer. So you are left with $n\le 9$ which has been done exhaustively by computer.

share|cite|improve this answer

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.