# The size of a graph is reconstructible from any n−2n−2 cards

Research paper by PaulBrown, TrevorFenner

Indexed on: 09 Nov '17Published on: 01 Jan '18Published in: Discrete Mathematics

#### Abstract

Let G<math class="math"><mi is="true">G</mi>[/itex] and H<math class="math"><mi is="true">H</mi>[/itex] be graphs of order n<math class="math"><mi is="true">n</mi>[/itex]. The number of common cards of G<math class="math"><mi is="true">G</mi>[/itex] and H<math class="math"><mi is="true">H</mi>[/itex] is the maximum number of disjoint pairs (v,w)<math class="math"><mrow is="true"><mo is="true">(</mo><mi is="true">v</mi><mo is="true">,</mo><mspace width="0.16667em" is="true"></mspace><mi is="true">w</mi><mo is="true">)</mo></mrow>[/itex], where v<math class="math"><mi is="true">v</mi>[/itex] and w<math class="math"><mi is="true">w</mi>[/itex] are vertices of G<math class="math"><mi is="true">G</mi>[/itex] and H<math class="math"><mi is="true">H</mi>[/itex], respectively, such that G−v≅H−w<math class="math"><mi is="true">G</mi><mo is="true">−</mo><mi is="true">v</mi><mo is="true">≅</mo><mi is="true">H</mi><mo is="true">−</mo><mi is="true">w</mi>[/itex]. We prove that if the number of common cards of G<math class="math"><mi is="true">G</mi>[/itex] and H<math class="math"><mi is="true">H</mi>[/itex] is at least n−2<math class="math"><mi is="true">n</mi><mo is="true">−</mo><mn is="true">2</mn>[/itex] then G<math class="math"><mi is="true">G</mi>[/itex] and H<math class="math"><mi is="true">H</mi>[/itex] must have the same number of edges when n≥29<math class="math"><mi is="true">n</mi><mo is="true">≥</mo><mn is="true">29</mn>[/itex]. This is the first improvement on the 25<math class="math"><mn is="true">25</mn>[/itex]-year-old result of Myrvold that if G<math class="math"><mi is="true">G</mi>[/itex] and H<math class="math"><mi is="true">H</mi>[/itex] have at least n−1<math class="math"><mi is="true">n</mi><mo is="true">−</mo><mn is="true">1</mn>[/itex] common cards then they have the same number of edges. It also improves on the result of Woodall and others that the numbers of edges of G<math class="math"><mi is="true">G</mi>[/itex] and H<math class="math"><mi is="true">H</mi>[/itex] differ by at most 1<math class="math"><mn is="true">1</mn>[/itex] when they have n−2<math class="math"><mi is="true">n</mi><mo is="true">−</mo><mn is="true">2</mn>[/itex] common cards.