Components of graph with edges given by congruence condition Let $G_n = (V_n, E_n)$ denote the graph with vertex set $V_n = \{0, 1, 2, \dotsc, n – 1\}$ and edge set $E_n = \left\{\{i, j\}: i + j \equiv 1 \pmod{n}\right\}$ where $n \ge 3$. How many components does $G_n$ have for $n \ge 3$? 
The answer is $\lceil n/2 \rceil$ if we allow loops. I've gotten the answer by making graphs for different values of $n$. Can anyone help with a constructive proof?
 A: Here is how I solved the problem. 
Since sum would be $n+1$. Patterns of edges would be like this: 
$(\lfloor{(n/2)}\rfloor, \lfloor{(n/2)}\rfloor +1), (\lfloor{(n/2)}\rfloor-1, \lfloor{(n/2)}\rfloor +2),...,(2,\lfloor{(n/2)}\rfloor+\lfloor{(n/2)}\rfloor
-1)$
Therefore total pairs $= \lfloor{(n/2)}\rfloor -1 -1+1 = \lfloor{(n/2)}\rfloor -1$
Considering trivial $(0,1)$ Total pairs or edges are $= \lfloor{(n/2)}\rfloor$. 
Now, with $n$ vertices & $k$ components a forest has $n-k$ edges. 
$\implies n - k = \lfloor{(n/2)}\rfloor$
$\implies k = n - \lfloor{(n/2)}\rfloor = 
\lceil{(n/2)}\rceil$
A: Since we are working $\bmod n$, I think it would be easier to name the vertices $\{1, \dotsc, n\}$ instead; the problem is the same. We see pretty quickly by playing around that the edges 
$$(1,n)\quad(2,n\!-\!1)\quad\dotsb\quad\left(\lfloor n/2\rfloor,  1+\lfloor n/2\rfloor\right)$$ 
must be in our graph. So there are at most $\lceil n/2 \rceil$ connected components, each component having one edge except for a single component with an isolated vertex if $n$ is odd. This is also all the components. On the contrary if we suppose that our graph has some edges $(a,b)$ and $(b,c)$ for distinct vertices $a$ and $c$, we would have
$$a+b \equiv 1  \quad\text{and}\quad b+c \equiv 1\;.$$ 
Subtracting these two congruence we get that $a\equiv c \pmod n$. But since our vertices are just $\{1,\dotsc,n\}$ this is only possible if $a=c$.
