Results 1 to 2 of 2

Math Help - Euler path and Euler circuit problem

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    11

    Question Euler path and Euler circuit problem

    For which n does K_n have an Euler path but not an Euler circuit?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2010
    From
    Florida
    Posts
    21

    There can be but one...

    Excluding the trivial edgeless case of K_1 we can proceed as follows:

    If n is odd
    Then K_n has all even degrees, and so by a theorem of Euler's we have that there exist an Eulerian circuit, which by technicality admits an Eulerian path (a circuit is a kind of path).

    If n is even
    Well clearly K_2 contains an Eulerian path but not an Euler circuit. However for all even n>2 we know that they have more than 2 vertices of odd degree (for K_n we have all vertices with degree n-1). For there to be an Eulerian path, we can have at MAX two vertices of odd degree, and for even n>2, this condition fails. And so K_2 is the only graph the has an Eulerian path but no circuit.

    For more info on Eulerian paths and circuits check out How can we tell if a graph has an Euler path or circuit?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: February 20th 2010, 08:26 AM
  2. Replies: 0
    Last Post: September 17th 2009, 06:44 PM
  3. euler phi problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 1st 2009, 07:53 PM
  4. Euler Path and Graph
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 26th 2009, 07:00 AM
  5. Euler & Hamiltonian Circuit proofs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 9th 2008, 07:16 PM

Search Tags


/mathhelpforum @mathhelpforum