# Thread: Graphs: Hemiltonian cycle/path

1. ## Graphs: Hemiltonian cycle/path

Hi!
I have two problems I should solve/prove in the subject of Hemiltonian cycles/paths.

1) Statement: We can create a cycle by using one pack of dominos. (domino rules: we have one brick, with two numbers (from 1 to 6) on each half of one side. we have to place the bricks next to each other, the numbers have to be the same where they "touch". E.g. we have two bricks: a 1-2 brick and a 3-2 brick. We can line them like: 1-2 and 2-3, hope you get the idea). How can I prove this statement?

2) Statement: We have a graph with more than 5 vertices. If this graph doesn't contain Hemiltonian cycle then nor does the complement of this graph. How can I prove this one?

Thanks a lot in advance!

P.s.:
Hopefully I got every mathematical expression right. English is not my native language.

2. ## Re: Graphs: Hemiltonian cycle/path

1) Need more information. Do you need to use all dominoes? I will represent dominoes using a pair of numbers (a,b). If you don't need to use all dominoes, then you can do this:

(1,2) - (2,3) - (3,4) - (4,1)
Arrange them so that they go in a square, and you have a cycle.

Alternatively, if you must use every domino, that is as simple as showing a cycle that uses all dominoes. Give an explicit arrangement that yields a cycle.

You have 21 dominoes: (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,3), (2,4), (2,5), (2,6), (3,3), (3,4), (3,5), (3,6), (4,4), (4,5), (4,6), (5,5), (5,6), (6,6)

Another way to word it, you have a multigraph on six vertices containing the complete graph on six vertices as a subgraph. Additionally, it contains a loop at each vertex (a loop is an edge going from the vertex to itself). Number these vertices 1 through 6. Now, each edge is a domino. Your question is equivalent to saying that there exists an Eulerian Cycle on this multigraph.

Eulerian Cycle -- from Wolfram MathWorld

Euler showed that there exists an Eulerian Cycle if and only if there exists no vertex with odd degree. Since the degree of every vertex is 7, no Eulerian Cycle exist.

2) This is false. You can disprove it with a counterexample. Start with the graph with 6 vertices and no edges. Its complement is the complete graph on 6 vertices. The complete graph on 6 vertices contains a Hamiltonian Cycle. Now, if you are talking connected graphs, that is another issue entirely.

#### Search Tags

discrete mathematics, graph, hamiltonian cycle, hamiltonian path 