Facebook Page
Twitter
RSS
All times are GMT -4. The time now is 09:47.
Results 1 to 5 of 5
  1. MHB Craftsman

    United States
    Status
    Offline
    Join Date
    Jul 2013
    Location
    Manteca, California
    Posts
    119
    Thanks
    78 times
    Thanked
    27 times
    #1
    Consider the complete graph with 5 vertices, denoted by K5.

    E.) Does K5 contain Hamiltonian circuits? If yes, draw them.

    I know that a Hamiltonian circuit is a graph cycle through a graph that visits each node exactly once. However, the trivial graph on a single node is considered to possess a Hamiltonian cycle, but the connected graph on two nodes is not. A graph possessing a Hamiltonian circuit is said to be a Hamiltonian graph.

    Is it correct that K5 doesn't contain Hamiltonian circuits because this is a connected graph on two nodes?

  2. MHB Apprentice

    Status
    Offline
    Join Date
    Feb 2012
    Posts
    36
    Thanks
    22 times
    Thanked
    7 times
    #2
    I have never done anything related with Graph Theory but with a google search for your problem I found this pdf, where it states that the number of Hamilton circuits in K(n) is
    (n-1)! [factorial]

    Hope the link will help you with the knowledge you have on graph theory!

    http://www.math.ku.edu/~jmartin/cour...ter6-part2.pdf

  3. Doctor Physicōrum
    MHB Math Helper
    MHB POTW Director
    MHB Ambassador

    United States
    Status
    Offline
    Join Date
    Jan 2012
    Location
    TX, USA
    Posts
    2,481
    Thanks
    5497 times
    Thanked
    5628 times
    #3
    It does not have two nodes, but five nodes. Any complete graph with more than two vertices has a Hamiltonian cycle: just go around the graph in order.
    Arma virumque canō, Trojae quī prīmus ab ōrīs Ītaliam fātō profugus Lāvīnaque vēnit lītora - multum ille et terrīs jactātus et altō vī superum, saevae memorem Jūnōnis ob īram, multa quoque et bellō passus, dum conderet urbem īnferretque deōs Latiō - genus unde Latīnum Albānīque patrēs atque altae moenia Rōmae. - Aeneid, by Publius Vergilius Maro.

  4. MHB Craftsman

    United States
    Status
    Offline
    Join Date
    Jul 2013
    Location
    Manteca, California
    Posts
    119
    Thanks
    78 times
    Thanked
    27 times
    #4
    Consider the complete graph with 5 vertices, denoted by K5.

    Does K5 contain Hamiltonian circuits? If yes, draw them.

    Is it correct to say that K5 does contain Hamiltonian circuits because it has more than two vertices?

  5. Doctor Physicōrum
    MHB Math Helper
    MHB POTW Director
    MHB Ambassador

    United States
    Status
    Offline
    Join Date
    Jan 2012
    Location
    TX, USA
    Posts
    2,481
    Thanks
    5497 times
    Thanked
    5628 times
    #5
    Quote Originally Posted by Joystar1977 View Post
    Is it correct to say that K5 does contain Hamiltonian circuits because it has more than two vertices?
    Well, having more than two vertices is not sufficient, by itself, to ensure that any particular graph contains a Hamiltonian circuit. It is necessary. However, because $K_{5}$, in addition to having more than two vertices, contains an edge from any vertex to any other vertex, it is quite straight-forward to construct a Hamiltonian circuit.
    Arma virumque canō, Trojae quī prīmus ab ōrīs Ītaliam fātō profugus Lāvīnaque vēnit lītora - multum ille et terrīs jactātus et altō vī superum, saevae memorem Jūnōnis ob īram, multa quoque et bellō passus, dum conderet urbem īnferretque deōs Latiō - genus unde Latīnum Albānīque patrēs atque altae moenia Rōmae. - Aeneid, by Publius Vergilius Maro.

Similar Threads

  1. Eulerian Circuits
    By Joystar1977 in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 13
    Last Post: August 9th, 2013, 20:12
  2. Euler circuits and mazes
    By Yuuki in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 1
    Last Post: June 22nd, 2013, 21:30
  3. [SOLVED] Probability of current flowing through circuits
    By Jameson in forum Basic Probability and Statistics
    Replies: 6
    Last Post: March 19th, 2013, 19:25
  4. Graph Theory. Decomposition of K_{2n+1} into hamiltonian cycles.
    By caffeinemachine in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 2
    Last Post: August 25th, 2012, 11:16

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards