Question

Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if |i-j|=8 or |i-j|=12. The number of connected components in G is
a)8
b)12
c)25
d)4

Answer 1

Answer on Question# 37458 - Math - Graph Theory

Let $G$ be a graph with 100 vertices numbered 1 to 100. Two vertices $i$ and $j$ are adjacent if $|i-j|=8$ or $|i-j|=12$. The number of connected components in $G$ is

a) 8

b) 12

c) 25

d) 4

Answer:

Consider the case $|i - j| = 8$:

then we could partition the graph as 8 sets, the vertices in each set are connected:

s1 $\{1,9,17,\ldots\}$ , i.e. all the vertices of form $8x + 1$ are connected to, $x >= 0$

s2 $\{2,10,18,\ldots\}$ i.e. all the vertices of form $8x + 2$ are connected, $x >= 0$

s3 $\{3,11,19,\ldots\}$ i.e. all the vertices of form $8x + 3$ are connected, $x >= 0$

s7 $\{7,15,\ldots\}$ i.e. all the vertices of form $8x + 7$ are connected, $x >= 0$

s8 $\{8,16,\ldots\}$ i.e. all the vertices of form $8x$ are connected, $x >= 1$

Now consider the case $|i - j| = 12$:

observe that 1 and 13 are connected, so s1, s5 together form a component

observe that 2 and 14 are connected, so s2, s6 together form a component

observe that 3 and 15 are connected, so s3, s7 together form a component

observe that 4 and 16 are connected, so s4, s8 together form a component

$\Rightarrow$ so total number of components are 4

Answer: d) 4.