The vertices of an undirected graph are numbered 1,2,...4286. The edge (i,j) exists if |i-j| <= 3, where i!=j. Which statements are true?

Question

The vertices of an undirected graph are numbered 1,2,...4286. The edge (i,j) exists if |i-j| <= 3, where i!=j. Which statements are true?

• the graph contains an Eulerian circle
• the graph contains a perfect matching graph
• the graph is Hamiltonian

I'm thinking that the last two are true, while the first one is false. Is this correct?

Answer 1

The graph is not an Eulerian cycle since such a cycle requires that every node has an even degree, but in this graph, node 1 has an odd degree -- its neighbors are 2, 3 and 4.

The graph contains a perfect matching: one possible match would be the collection of edges that connects to +1, for each odd :

1─2, 3─4, 5─6, ... , 4285─4286

The graph is a Hamiltonian graph, as it contains the following Hamiltonian cycle:

1─2 ─ 4─5 ─ 7─8 ─ 10─11 ─ 13─14 ─ ...    ─ 4282─4283 ── 4285─4286   
 \                                                            /
  ─ 3 ─── 6 ─── 9 ──── 12 ──── ... ─── 4281 ─────── 4284 ─────

So at the bottom we have all multiples of 3, and at the top all the other values.