1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler circuit in a directed multigraph

Tags:
  1. Jun 19, 2016 #1
    1. The problem statement, all variables and given/known data
    So the question is:
    Show that a directed multigraph having no isolated vertices has an Euler circuit if and only if the graph is weakly connected and the in degree and out degree of each vertex are equal.


    2. Relevant equations
    Euler circuit: A circuit that has all edges of the graph, which aren't repeated and the circuit ends on the same vertex, where it started.
    Weakly connected graph: A graph, whose underlying undirected graph is connected.(For digraphs only.)
    In-degree: Number of incident edges,on a vertex, in a digraph.
    Out-degree: Number of outgoing edges, from a vertex, in a digraph.

    3. The attempt at a solution
    Since there is a biconditional in the question, we can write it as
    ##p←→q##(←→ represents the biconditional)
    Where ## p## is: A directed multigraph having no isolated vertices has an Euler circuit .
    And ##q## is: The graph is weakly connected and the in degree and out degree of each vertex are equal.
    So we can prove the given statement by proving:
    1)##p→q##, and
    2)##q→p##
    The problem, I am facing is that, when we prove the 1st part, we have to show that Euler circuit in a directed multigraph is weakly connected. I am failing to see, how that is possible. If there is an Euler circuit present in the digraph, then reaching vertex to another is easily possible, moreover coming back is too, which makes the graph strongly connected.
    One more thing, every strongly connected graph is also a weakly connected graph. I don't think this question is trying to trick me on that, but still, It can. All questions are evil, until solved.
    Moon
     
  2. jcsd
  3. Jun 20, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I don't think you are interpreting the question quite correctly. You are reading it as something like:
    Whereas I think what it is saying is:
    So you are asked to prove that:
    $$DirectedMultiGraph(G)\wedge NoIsolatedVertices(G)\wedge (NumEulerCircuits(G)\geq 1) \leftrightarrow
    DirectedMultiGraph(G)\wedge NoIsolatedVertices(G)\wedge WeaklyConnected(G)\wedge (\forall v\in V(G):\ InDegree(v)=OutDegree(v))$$

    Also, if you can prove StronglyConnected then you have also proven WeaklyConnected since the former entails the latter (but not vice versa). The usual convention in mathematics is that Weakly-X or Partially-X is entailed by Strongly-X, Totally-X or just plain X, but not vice versa.
     
  4. Jun 20, 2016 #3
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Euler circuit in a directed multigraph
  1. Euler's method (Replies: 1)

  2. Euler's Method (Replies: 6)

  3. Euler Constant (Replies: 9)

  4. Euler's Method (Replies: 5)

  5. Euler's Approximation (Replies: 2)

Loading...