Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: Graphs: Hemiltonian cycle/path

  1. #1
    Mar 2018

    Graphs: Hemiltonian cycle/path

    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!

    Hopefully I got every mathematical expression right. English is not my native language.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Nov 2010

    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.
    Thanks from DaisyDoodle
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] m cycle
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Oct 4th 2011, 11:25 PM
  2. Replies: 0
    Last Post: Aug 24th 2010, 05:48 PM
  3. Yen's algorithm - shortest path - Graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 12th 2009, 11:52 AM
  4. degree of a path, path homotopy.
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: Mar 19th 2009, 05:37 PM
  5. Replies: 2
    Last Post: Dec 9th 2007, 02:33 PM

Search Tags

/mathhelpforum @mathhelpforum