Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have knowledge of the necessary and sufficient condition for an undirected graph contains a Hamiltonian cycle and an Eulerian circuit, but is there a necessary and sufficient condition for directed graphs?

common sense tells me that the degree of input minus output degree of each vertex must be zero, but do not know if I'm right (this is for the euler circuit)

share|improve this question
    
The graph has a finite set of vertices –  franvergara66 Nov 13 '11 at 5:18

1 Answer 1

up vote 3 down vote accepted

If you can find Hamiltonian cycles in an undirected graph, you can find them in directed graphs too by replacing each vertex by a linear sequence of three vertices *---*---* and connect all incoming edges to one of the end nodes and all the outgoing edges to the other end node. After that you don't need to remember the direction of the edges.

For an Eulerian circuit, you need that every vertex has equal indegree and outdegree, and also that the graph is finite and connected and has at least one edge. Then you should be able to show that

  • a non-edge-reusing walk of maximal length must be a circuit (and thus that such circuits exist), and
  • a non-edge-reusing circuit that doesn't use all edges can always be extended, and thus that such a circuit of maximal length must necessarily contain all edges.
share|improve this answer
    
Sorry to nitpick, but doesn't a finite connected digraph always contain at least one edge? (Unless it has a single vertex, in which case it does technically have an Eulerian circuit.) –  jwg Aug 22 at 20:37
    
@jwg: Hmm, yes. –  Henning Makholm Aug 24 at 4:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.