Hamiltonian paths and cycles

Hamiltonian means every vertex

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle visits every vertex once and returns to its start. Here cycles are in simple undirected graphs with at least three vertices. Check each consecutive pair for adjacency; unused edges are allowed. A path on n vertices uses n − 1 edges and a cycle uses n edges

Which is a Hamiltonian cycle in the square with diagonal AC?

A Hamiltonian path visits seven vertices. How many edges does the path use?

A witness proves existence

Exhibit a vertex sequence and check every required adjacency, complete vertex coverage and permitted endpoints. That proves existence. Failed attempts do not prove impossibility: either exhaust all distinct candidates with a justified search, or give a structural obstruction. Eulerian degree parity is not a Hamiltonian test

The two triangles share only A. Which statement is correct?

Leaves, bridges and cut vertices

Every vertex of a Hamiltonian cycle uses two different incident edges, so a degree-one vertex rules a cycle out. A bridge cannot belong to a cycle, and a Hamiltonian cycle visiting both sides would need it, so any bridge rules a cycle out. More generally, deleting a vertex from a Hamiltonian cycle leaves a spanning path; therefore a graph with a cut vertex cannot have a Hamiltonian cycle. These are necessary conditions, not a complete existence test

Construct a path and disprove a cycle, ungraded

Two triangles ABC and DEF are joined only by edge CD. Write a Hamiltonian path. Prove that there is no Hamiltonian cycle. State whether an Eulerian trail exists as a separate question. Independent route and proof construction are ungraded

Model: path, cycle obstruction and Eulerian route

Triangles ABC and DEF are joined only by CD. A-B-C-D-E-F is a Hamiltonian path: it follows five edges and lists all six vertices once. CD is a bridge, so a cycle visiting both triangles would have to cross CD and later cross it again, which is forbidden. Thus there is no Hamiltonian cycle. Separately, only C and D have odd degree, so an Eulerian trail exists, for example C-A-B-C-D-E-F-D.

Count complete-graph tours without duplicates

In a complete simple undirected graph on n ≥ 3 labelled vertices, fix a starting vertex. List the other n − 1 vertices in any order, then return to the start. All consecutive pairs are edges. Fixing the start removes rotational duplicates, but each tour is still listed twice, once in each direction. Thus the number of distinct undirected Hamiltonian cycles is half the factorial of one less than the number of vertices. The factorial means the product of the positive integers up to n − 1. This formula counts complete-graph cycles, not cycles in every graph

In K5, count undirected Hamiltonian cycles, treating reversal and a different starting point as the same cycle

Compare all tours on four vertices, ungraded

A complete undirected network has symmetric travel times AB = 4, BC = 7, CD = 3, DA = 6, AC = 5 and BD = 9 minutes. A route must start at A, visit B, C and D once each and return to A. List every tour up to reversal, calculate its time and justify the minimum. State why comparing only two guessed tours would be insufficient. This modelling and exhaustive argument are ungraded

Model: the three distinct tours

The symmetric travel times are AB = 4, BC = 7, CD = 3, DA = 6, AC = 5 and BD = 9 minutes. Fix A. The six orders of B, C and D pair into three reversals. A-B-C-D-A costs 4 + 7 + 3 + 6 = 20 minutes. A-B-D-C-A costs 4 + 9 + 3 + 5 = 21 minutes. A-C-B-D-A costs 5 + 7 + 9 + 6 = 27 minutes. The first tour, or its reverse, is optimal at 20 minutes because the list covers every admissible tour. The model assumes symmetric, fixed, additive times and requires every visit exactly once; congestion or revisits could change the problem

An inspection covers every corridor; a delivery tour visits every room once and returns. Which models fit?