Question

Find a directed graph that is not Eulerian but for which the underlying graph is Eulerian.

Short answer

Construct a directed graph where vertex degrees mismatch in in-degree and out-degree, yet even degree when undirected.

Step-by-step solution

Understanding Eulerian Graph

An Eulerian circuit in a graph is a circuit that visits every edge exactly once and returns to the starting vertex. A directed graph is Eulerian if every vertex has equal in-degree and out-degree, and all its vertices with nonzero degree are strongly connected. The underlying graph of a directed graph is the graph obtained by replacing every directed edge with an undirected one.

Check Eulerian Conditions for the Underlying Graph

For an undirected graph to have an Eulerian circuit, it must be connected and have a degree that is even for all vertices. In this exercise, we need a directed graph whose underlying graph satisfies these properties.

Construct the Directed Graph

Let's construct a simple directed graph with three vertices: A, B, and C. Consider the edges: A -> B, B -> C, C -> A, and also an extra edge B -> A. This set of directed edges ensures each vertex has at least one edge going in and out.

Evaluate the Directed Graph

In our directed graph, vertex A has out-degree 1 and in-degree 2, vertex B has out-degree 2 and in-degree 1, and vertex C has out-degree 1 and in-degree 1. Since the in-degrees and out-degrees are not equal for all vertices, the directed graph is not Eulerian.

Check the Underlying Graph

Convert the directed edges into undirected edges, yielding the underlying graph. Here, vertices A, B, and C have even degrees (each degree 2), and the graph remains connected. Hence, the underlying graph is Eulerian because it satisfies the conditions for an undirected Eulerian circuit.

Key concepts

Directed Graphs

A directed graph, or digraph, consists of a set of vertices connected by edges, where each edge has a direction specified. This direction implies that the edges can only be traversed in a specific way—typically represented by arrows between the vertices.
In a directed graph:

• Every edge has a starting point (source) and an ending point (destination).
• The direction of edges matters, unlike undirected graphs that exhibit bi-directional edges.
• Applications of directed graphs are vast, including modeling real-world processes such as web page linking, social media networks, and computer networks.

When analyzing properties of directed graphs, it is essential to focus on the roles of each vertex as a point of origin or destination for the edges. This focus on vertex roles directly influences calculations involving graph properties, such as in-degrees and out-degrees.

In-degree and Out-degree

In the context of directed graphs, an understanding of both in-degree and out-degree is fundamental.
**In-degree** refers to the number of edges that are directed into a vertex. It represents the count of arrows pointing towards the vertex, offering insights into how many connections it receives.
**Out-degree**, on the other hand, is the count of edges that are directed out from a vertex. This metric indicates the number of outgoing connections a vertex possesses.
To determine if a directed graph is Eulerian:

• Every vertex must have an in-degree equal to its out-degree.
• The graph should also be strongly connected, meaning there is a path between any two vertices, traversing the edges in their respective directions.

The balance of in-degree and out-degree ensures that traversal can start and end at the same vertex, looping through each edge exactly once without leaving any vertex inaccessible.

Undirected Graph

An undirected graph is distinguished by edges that do not have a specific direction. In this type of graph:

• Each edge represents a bi-directional or mutual relationship between two vertices.
• The concept of edge directionality in directed graphs is removed, resulting in a simpler model.

For an undirected graph to be Eulerian:

• All vertices with non-zero degree must be connected, forming one single component.
• Each vertex must have an even degree.

The simplicity of undirected graphs makes them favorable for modeling symmetric relationships or connections where directionality is not a primary concern. The requirement for even-degree vertices ensures cyclic paths can be formed that revisit vertices without repetition. This property facilitates the formation of Eulerian tours, which visit each edge once and return to the starting vertex.