I am reading this paper and trying to understand why Theorem 1.1 guarantees a perfect matching for the prime sum graph as stated at the bottom of page 2. Can anyone provide some insight?

Thanks so much!

  • $\begingroup$ A perfect matching is a partition of vertices into pairs such that each pair forms an edge. That is exactly what Thm 1.1 is saying. $\endgroup$ – Michal Adamaszek May 9 at 14:13
  • $\begingroup$ Thank you! So does this mean that each pair is connected by an edge in a different set? $\endgroup$ – Lena May 9 at 14:16
  • $\begingroup$ I don't know what you mean. A pair is an edge in the graph. $\endgroup$ – Michal Adamaszek May 9 at 14:18
  • $\begingroup$ Sorry I should've been more clear. Is each edge connecting the numbers in the pair in a different class? I'm thinking of a perfect matching as a graph where there exists a set of edges such that every vertex is incident with exactly one edge from the set. How does the set of edges relate to the pairs? $\endgroup$ – Lena May 9 at 14:26

Let $q$ be a prime satisfying $2n < q <4n$. There always exists such a prime, by Chebychev's Thm proved in 1852 (formerly known as Bertrand's postulate). Then for each $i =0,1,2,\ldots q-2n$, match $2n-i$ with $q-2n+i$. Then note that $q-2n$ is an odd integer strictly less than $2n$ and that every integer in $[q-2n,q-2n+1,\ldots,2n-1, 2n]$ is matched. Thus, for some even integer $m<n$, the set of integers not yet matched are precisely those in the set $\{1,\ldots, 2m\}$. Can you finish from here?

[For $n=1$ note that $1+2=3$ a prime.]

  • 1
    $\begingroup$ Thanks so much! $\endgroup$ – Lena May 10 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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