Let G be a graph with V={1,2,...100}, where x,y have an edge connecting them if |x-y|=2 or |x-y|=8.

Is G connected? Prove your claim.

A connected graph is a graph in which for any 2 vertices there is a path connecting them.

Question

Let G be a graph with V={1,2,...100}, where x,y have an edge connecting them if |x-y|=2 or |x-y|=8.

Is G connected? Prove your claim.

A connected graph is a graph in which for any 2 vertices there is a path connecting them.

anonymous · Answer

I just thought of something. If 2 vertices are only connected when you have a difference of 2 or 8 (both of which are even) then any odd vertex can't be connect to any even vertex (since an even and an odd number can only have an odd difference). This means that the graph is not connected.