Graph Theory

Simple Graphs

A graph with no loops or parallel edges is called a simple graph.

simple graph. A graph ${G = (V,E)}$ is simple if, and only if, ${G}$ consists of only ${V}$ and ${E,}$ and ${E}$ contains no loops and no parallel edges. That is, for all ${\set{a,b} \in E,}$ ${\set{a,b} = \set{b,a}}$ and ${\set{a,a} \notin E.}$

In the next section we discuss digraphs, where we introduce the notion of directed edges. Per the definition above, simple graphs have no direction. We can also see that given a simple graph ${G_s,}$ there are, at most, ${(\card{V}(\card{V}-1))/2}$ edges. This is because ${\card{V}^2,}$ the Cartesian product of ${V,}$ includes self-loops and counts each edge between distinct vertices. Thus, we subtract ${V}$ and divide by 2.

theorem. Given a simple graph ${G = (V,E)}$ with ${n \in \nat}$ vertices, there are, at most, ${\dfrac{n(n - 1)}{2}}$ edges.

This bound is partly why simple graphs are the most widely-used type of graph. The bound no longer exists once we allow parallel edges.

density of a simple graph. Given a simple graph ${G,}$ the density of ${G}$ is defined as ${\df{density}(G)=(2 \by \card{E})/(\card{V}),}$ where ${\card{E}}$ is the number of edges, and ${\card{V}}$ is the number of vertices.

Subgraphs

In some cases, we're only interested in just a few parts of a graph ${G,}$ rather than the entirety of ${G.}$ Those parts are called subgraphs.

subgraph. Given a graph ${G=(V,E),}$ a subgraph of ${G}$ is a graph ${G' = (V',E'),}$ such that ${V' \subseteq V}$ and ${E'\subseteq E.}$

The definition above is for a simple graph. Given an edge ${e = (a,b)}$ we say that ${a}$ and ${b}$ are neighbors or adjacent, and we say that ${e}$ is incident to ${a}$ and ${b.}$

Walks

A sequence of vertices and edges is called a walk.

walk. Let ${G=(V_G, E_G)}$ be a graph of ${n \in \nat}$ vertices. A walk is a sequence ${W = (v_1, e_1, v_2, e_2, v_3, e_3, \ldots, v_{n-1}, e_{n-1}, v_n)}$ where each ${v_i \in V_G}$ and ${e_i \in E_G}$ for all ${0 \le i \le n}$ We define the number of edges in ${W}$ as the length of the walk.

Paths

A sequences of vertices and edges with no repeated vertices is called a path.

path. Let ${G=(V_G, E_G)}$ be a graph of ${n \in \nat}$ vertices. ${G}$ contains a path if, and only if, there exists a walk ${P=(v_1, e_1, v_2, e_2, \ldots, v_{n-1}, e_{n-1}, v_n)}$ where each ${v_i \in P}$ is distinct, for all ${1 \le i \lt n.}$ We denote the set of all vertices comprising ${P}$ with ${\v(P),}$ and the set of all all edges as ${\e(P).}$

vertex disjoint paths. Two paths ${P}$ and ${Q}$ are vertex disjoint if and only if ${\v(P) \cap \v(Q) = \nil.}$

edge disjoint paths. Two paths ${P}$ and ${Q}$ are edge disjoint if and only if ${\e(P) \cap \e(Q) = \nil.}$

disjoint paths. Two paths ${P}$ and ${Q}$ are disjoint if, and only if, they are both vertex disjoint and edge disjoint.

A Hamiltonian path on a graph ${G}$ is a path on ${G}$ containing every vertex of ${G.}$

hamiltonian path. A path ${P}$ on a graph ${G=(E,V)}$ is a Hamiltonian path if, and only if, ${\v(P) = \v(G).}$

Trails

A walk with no repeated edges is called a trail. If the first and the last vertices are equal, we call the walk a closed trail.

trail. Let ${G=(V_G, E_G)}$ be a graph of ${n \in \nat}$ vertices. ${G}$ contains a trail if, and only if, there exists a walk ${T=(v_1, e_1, v_2, e_2, v_3, e_3, \ldots, v_{n-1}, e_{n-1}, v_n)}$ where each ${e_i \in T}$ is distinct, for all ${1 \le i \lt n.}$ If ${v_n = v_1}$ (that is, a loop) we say that ${T}$ is a closed trail.

Circuits

A circuit is a trail that starts and finishes at the same node.

circuit. Given a graph ${G=(V_G, E_G)}$ with ${n \in \nat}$ vertices, we say that ${G}$ contains a circuit if, and only if, there exists a trail ${T=(v_1, e_1, v_2, e_2, v_3, e_3, \ldots, v_{n-1}, e_{n-1}, v_n)}$ such that ${v_n = v_1,}$ for all ${1 \le i \lt n,}$

Cycles

A cycle is a circuit where the only repeated vertices are the first and the last.

cycle. Let ${G=(V_G, E_G)}$ be a graph of ${n \in \nat}$ vertices. ${G}$ a cycle if, and only if, there exists a circuit ${T=(v_1, e_1, v_2, e_2, v_3, e_3, \ldots, v_{n-1}, e_{n-1}, v_n),}$ where ${v_1 = v_n}$ and ${v_1}$ is the only repeated vertex for all ${1 \le i \lt n.}$ If ${G}$ contains a cycle, then we say that ${G}$ is called cyclic. Otherwise, we say that ${G}$ is acyclic.

Some cycles have a special property of containing every vertex of ${G.}$ We call these cycles Hamiltonian cycles.

hamiltonian cycle. A cycle ${C}$ on a graph ${G}$ is a Hamiltonian cycle if, and only if, ${\v(C)=\v(G).}$

Connectedness

Graphs are called connected if it contains a path from every vertex to every other vertex. That is, there exists a path if we wanted to visit every single vertex.

connectedness. A graph ${G=(V_G,E_G)}$ is connected if, and only if, for any two vertices ${x,y \in V_G,}$ there exists a path whose endpoints are ${x}$ and ${y.}$ Otherwise, we say that ${G}$ is disconnected.

For a digraph ${D,}$ if we can can visit every vertex in the correct direction, we call ${D}$ a strongly-connected graph.

strong-connectedness. A digraph ${D=(V_G,E_G)}$ is strongly-connected if, and only if, there exists a walk ${W=(v_1, e_1, v_2, e_2, v_3, e_3, \ldots, v_{n-1}, e_{n-1}, v_n),}$ such that, if ${v_i \in V_G,}$ then ${W(v_i) = v_i}$ and ${A(v_i) = v_i,}$ where ${A}$ is the adjacency function of ${D.}$ Otherwise, we say that ${D}$ is weakly-connected.

Trees

tree. A graph ${T}$ is called a tree if, and only if, ${T}$ is acyclic and ${T}$ is connected.

The spanning tree of a tree ${T}$ is a tree that contains all of ${T}$'s vertices, but not necessarily edges.

spanning tree. Given a tree ${G,}$ a spanning tree of ${G,}$ denoted ${t[G],}$ is a tree ${(v_t, e_t),}$ where ${v[t] = V[T]}$ and ${e_s \subseteq E[T].}$

forest. A forest ${F}$ is a set ${\set{T_1, T_2, \ldots, T_n},}$ where each ${T_i}$ is a tree for all ${1 \le i \lt n}$ with ${n \in \nat.}$

spanning forest. Given a tree ${T,}$ the spanning forest of ${T,}$ denoted ${\df{sf}[T],}$ is a set ${\set{t_1, t_2, \ldots, t_n},}$ where each ${t_i}$ is a spanning tree of ${T}$ for all ${1 \le i \lt n}$ with ${n \in \nat.}$

Graph Operations

complete graph. A graph ${G = (V,E)}$ is a complete graph if, and only if, for any ${a \in V}$ and any ${b \in V,}$ there exists an edge ${(a,b) \in V.}$ We denote a complete graph with the notation ${G[V]^2.}$

graph complement. Given a graph ${G = (V,E),}$ the complement of ${G,}$ denoted ${\nix{G},}$ is defined as ${\nix{G} = G[E] \smallsetminus G[V]^2.}$

graph union. Given the graph ${G_1 = (V_1,E_1)}$ and ${G_2 = (V_1,E_2),}$ the union of ${G_1}$ and ${G_2}$ is defined as ${G_1 \cup G_2 = E_1 \cup E_2.}$

Digraphs

Graphs can be directed or undirected. Directed graphs are also called digraphs. For example:

Here, the edges are directed a particular way. By definition, an edge ${(e,g)}$ exists if and only if an edge ${(g,e)}$ exists. The "arrowhead" is determined by a function called the adjacency function. This function tells us that a directed edge ${(e,g)}$ exists, but not ${(g,e).}$

digraph. A digraph ${D}$ is an ordered triple ${(V_D, E_D, A_D),}$ where ${V_D}$ is a set of vertices, ${E_D}$ is a set of directed edges. The function ${A_D}$ is a mapping called the arrow function of ${D,}$ such that ${A_D : E_D \mapsto V_D \times V_D}$ associates each directed edge with an ordered pair of vertices. Given a directed edge ${(u,v),}$ where ${u}$ and ${v}$ are vertices of ${V_D,}$ we call ${u}$ the edge's source, and ${v}$ the edge's destination. Given a vertex ${v \in V_D,}$ the number of edges such that ${v}$ is a source is called the outdegree of ${v,}$ denoted ${\df{odeg}(v).}$ The number of edges such that ${v}$ is a destination is called the indegree of ${v,}$ denoted ${\df{indeg}(v).}$