CODEWITHSUNDEEP
algorithmgraphgraph-theorygraph-algorithmhamiltonian-cycle
aneys
aneys

Reputation: 73

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 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?

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

Upvotes: 1

Views: 48

Answers (1)

trincot
trincot

Reputation: 350272

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.

Upvotes: 3

Related Questions