We will first define the most fundamental of graphs, a simple graph:
|Definition: A Simple Graph $G$ is an ordered pair $G = (V, E) = (V(G), E(G))$ where $V$ is a non-empty set containing information regarding the Vertices of $G$, and $E$ is a set $E \subseteq [ V ]^2$ containing the information on the Edges in $G$.|
We will graphically denote a vertex with a little dot or some shape, while we will denote edges with a line connecting two vertices. Note that these edges do not need to be straight like the conventional geometric interpretation of an edge. For example, the following graphs are simple graphs.
|Definition: A Multigraph is a graph $G$ that contains either multiple edges or loops.|
We consider a multiple edge to be to lines from a vertex $x$ to a vertex $y$. One the other hand, we consider a loop to be an edge that wraps around back to itself.
The following graphs are multigraphs:
Digraphs (Directed Graphs)
|Definition: A Digraph is a graph $D$ that contains directed edges (also called arcs) instead of regular edges.|
We note that a directed edge (or arc) contains some sort of direction from one vertex to another:
The following graphs are digraphs:
|Definition: A Subgraph $S$ of a graph $G$ is a graph whose vertex set $V(S)$ is a subset of the vertex set $V(G)$, that is $V(S) \subseteq V(G)$, and whose edge set $E(S)$ is a subset of the edge set $E(G)$, that is $E(S) \subseteq E(G)$.|
Essentially, a subgraph is a graph within a larger graph. For example, the following graph $S$ is a subgraph of $G$: