 # Discrete Maths Graph theory

#1

What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?

#2

The exact condition you need is that every vertex must be reachable from the start vertex (except for any vertices with in-degree and out-degree 00, which we don’t care about when looking for an Euler path). Equivalently, every edge must be reachable from the start vertex. That is, for every edge, there is a path from the start vertex including that edge.

This condition is clearly necessary; if an edge is not reachable from the start vertex, you can never include that edge in a directed path.

#3

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.

#4

You can verify that this condition is sufficient by checking that a modified version of Hierholzer’s algorithm will find an Euler path.

Hierholzer’s algorithm, modified for Euler paths in directed graphs, starts by taking an arbitrary path from the start vertex to the end vertex. Then, as long as there are vertices on the path with unused out-edges, we:

Start at one of these vertices and keep taking unused out-edges until we return to that vertex, creating a directed cycle;
Splice that cycle into our path from the start vertex to the end vertex, creating a longer path.
The degree condition ensures that we never get stuck in step 1. But it’s the connectedness condition given above that ensures that, as long as there are unused edges anywhere in the graph, there must be unused edges leaving vertices on the path we’ve found.

#5

The exact condition you need is that every vertex must be reachable from the start vertex (except for any vertices with in-degree and out-degree 00, which we don’t care about when looking for an Euler path). Equivalently, every edge must be reachable from the start vertex. That is, for every edge, there is a path from the start vertex including that edge.

This condition is clearly necessary; if an edge is not reachable from the start vertex, you can never include that edge in a directed path. You can verify that this condition is sufficient by checking that a modified version of Hierholzer’s algorithm will find an Euler path.

Hierholzer’s algorithm, modified for Euler paths in directed graphs, starts by taking an arbitrary path from the start vertex to the end vertex. Then, as long as there are vertices on the path with unused out-edges, we:

Start at one of these vertices and keep taking unused out-edges until we return to that vertex, creating a directed cycle;
Splice that cycle into our path from the start vertex to the end vertex, creating a longer path.
The degree condition ensures that we never get stuck in step 1. But it’s the connectedness condition given above that ensures that, as long as there are unused edges anywhere in the graph, there must be unused edges leaving vertices on the path we’ve found.

#6

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.

``  Or in simple we can say. - "I have come across the theorem A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree. I just want to know whether the same holds for connected simple graphs as well. "``