Subdigraphs And Underlying Graphs

# Subdigraphs

Definition: For a digraph $G = (V(G), E(G))$, a Subdigraph of $G$ is a digraph whose vertices and arcs are also $G$. |

For example, let's take a look at the following digraph:

One possible subdigraph of the graph above is:

Notice that this subdigraph contains arcs which are also in the original graph. Direction of the arcs matters though. For example, the following digraph:

Is NOT a subdigraph of the first graph, as the direction of one of the arcs (the blue one) is not the same as the original graph.

# Underlying Graphs

Definition: For a digraph $G = (V(G), E(G))$, the Underlying Graph of $G$ is the undirected graph created using all of the vertices in $V(G)$, and replacing all arcs in $E(G)$ with undirected edges. |

For example, let's look at the following digraph on $4$ vertices and $5$ arcs:

The corresponding underlying graph would look like this: