Graphs and Subgraphs

# 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\$: 