# How do we know that the prime sum graph defined in this paper has a perfect matching?

https://arxiv.org/pdf/1804.07104.pdf

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!

• 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. – Michal Adamaszek May 9 at 14:13
• Thank you! So does this mean that each pair is connected by an edge in a different set? – Lena May 9 at 14:16
• I don't know what you mean. A pair is an edge in the graph. – Michal Adamaszek May 9 at 14:18
• 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? – 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, 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.]