Simple Graphs
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.
Multigraphs
| 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:
Subgraphs
| 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$:
