How to find connected components of a random graph?

finding a formula for the number of connected components in a graph

• Let $n$ and $k$ be integers with $1\le k < n$. Form a graph $G$ whose vertices are the integers $0,1,2,...,n-1$. We have an edge joining the vertices $a$ and $b$ provided $$a-b \equiv \pm k \pmod n\;.$$ We were given the example if $n=20$ and $k=6$, then vertex $2$ would be adjacent to vertices $8$ and $16$. I need to find a formula involving $n$ and $k$ for the number of connected components of $G$. I tried creating other examples, with $k=1$ and $n=2$, with $k=2$ and $n=20$, etc, and the pattern that I seemed to find was that the number of components was equal to $k$. But I know that this cannot be the correct solution since $n$ is not involved in this formula, so I also tried $n \bmod k$ as the formula, which seemed to work. Is $n \bmod k$ a legitimate formula for the number of connected components of $G$?

• Answer:

  Start at vertex $0$; it's adjacent to $k\bmod n$. From there you can go to $2k\bmod n$, then to $3k\bmod n$, and so on. There are only finitely many vertices, so at some point you must return to one that you've already visited. Show that you return to $0$ at step $m$, where $m$ is the smallest positive integer such that $mk$ is a multiple of $n$. Then show that $m=n/d$, where $d=\gcd(k,n)$. Thus, you've traced out a cycle of length $n/d$, and that cycle is clearly a connected component of $G$. Show that much the same thing happens no matter where you start: you trace out a cycle of length $n/d$. If you can do that, you should have little trouble figuring out how many connected components $G$ has. You may find it helpful to look at the cases $n=10,k=6$ and $n=21,k=15$.