Introduction to Graph Theory

A graph is a pair $G = (V, E)$ , it consists of a finite set $V$ of objects called the vertices (or nodes or points) and a set $E$ of 2-elements subsets of $V$ called edges, another way to denote the vertex set/edges of a graph $G$ is using $V (G)$ (the vertex set of $G$ ) and $E (G)$ (the edge set of $G$ )

\begin{aligned} G & = (V, E) \\ V & = {1, 2, 3, 4, 5, 6, 7} \\ E & = {{1, 5}, {5, 7}, {2, 3}, {2, 4}, {3, 4}} \end{aligned}

Properties

the order of a graph is the number of vertices (written as $∣ G ∣$ )
the size of a graph is the number of edges (written as $‖ G ‖$ )
an edge $u, v$ is usually written as $u v$ (or $v u$ ), if $u v$ is an edge of $G$ then $u$ and $v$ are said to be adjacent in $G$
a vertex $v$ is incident with an edge e if $v \in e$
the set of neighbors of a vertex $v$ is denoted by $N (v)$
the degree of a vertex $v$ is the number of edges incident to $v$ (loops are counted twice)

Let $G = (V, E)$ and $G^{'} = (V^{'}, E^{'})$ be two graphs, we set $G \cup G^{'} = (V \cup V^{'}, E \cup E^{'})$ and $G \cap G^{'} = (V \cap V^{'}, E \cap E^{'})$

if $G \cup G = \emptyset$ then $G$ and $G^{'}$ are disjoint
if $V^{'} \subseteq V$ and $E^{'} \subseteq E$ then $G^{'}$ is a subgraph of $G$ written as $G^{'} \subseteq G$
if $G^{'}$ is a subgraph of $G$ and either $V^{'} \subset V$ or $E^{'} \subset E$ then $G^{'}$ is a proper subgraph of $G$
if $G^{'}$ is a subgraph of $G$ and $V^{'} = V$ then $G^{'}$ is an spanning subgraph of $G$
if $V^{'} \subseteq V$ and all the edges $e = u v \in E$ so that $u \in V^{'}$ and $v \in V^{'}$ and also $e \in E^{'}$ then $G^{'}$ is an induced graph of $G$

Movement

A walk in a graph is a sequence of movements beginning at $u$ moving to a neighbor of $u$ and then to a neighbor of that vertex and so on until we stop at a vertex $v$

W = (u = v_{0}, v_{1}, \dots, v = v_{k})

where $k \geq 0$ , note that there are no restrictions on the vertices visited so a vertex can be visited more than once also there are no restrictions on the edges traversed so an edge can be traversed more than once, every two consecutive vertices in $W$ are distinct since they are adjacent, if $u = v$ then we said that the walk is closed otherwise it’s open

a trail is a walk in which no edge is traversed more than once
a path is a walk in which no vertex is visited more than once (note that every path is also a trail)
a circuit is a closed trail of length 3 or more (it begins and ends at the same vertex but repeat no edges)
a cycle is a circuit that repeat no vertex (think of it as a closed path), a $k$ -cycle is a cycle of length $k$ (e.g. a $3$ -cycle is a triangle)

Properties related with path lengths

the distance between two vertices $u$ and $v$ is the smallest length of any $u - v$ path in $G$ denoted by $d (u, v)$
the diameter is the greatest distance between any two vertices of a connected graph

Some additional properties related with connectivity in a graph

if a graph $G$ contains a $u - v$ path then $u$ and $v$ are said to be connected
a graph $G$ is connected if every two vertices of $G$ are connected
a connected subgraph of $G$ that is not a proper subgraph of any other connected subgraph of $G$ is a component of $G$
the number of components of a graph is denoted by $k (G)$ , then a graph is connected if $k (G) = 1$

Common classes of graphs

Complete graph

A graph $G$ is complete if every two distinct vertices of $G$ are adjacent

a complete graph of order $n$ is denoted by $K_{n}$ , for complete graphs $K_{n}$ has the maximum possible size for a graph of $n$ vertices
the number of pairs of vertices in $K_{n}$ is $(\binom{n}{2}) = \frac{n (n - 1)}{2}$

Sparse graph

A graph $G$ of order $n$ and size $m$ is a sparse graph if $m$ is close to the minimal number of edges i.e. when $m \approx n$ , in this case adjacency lists are prefered since they require constant space for every edge, a tree is a good example of a sparse graph

Dense graph

A graph $G$ of order $n$ and size $m$ is a dense graph if $m$ is close to the maximal number of edges i.e. when $m \approx n^{2}$ , in this case an adjacency matrix is prefered, a complete graph is a dense graph

Complement graph

The complement $\bar{G}$ of a graph $G$ is a graph whose vertex is the set $V (G)$ and such that for each pair $u, v$ of distinct vertices, $u v \in E (\bar{G})$ and $u v \notin E (G)$ , that means that the complement of a complete graph is a graph of order $n$ and size $0$

if $G$ is diconnected, $\bar{G}$ is connected

Bipartite graph

A graph $G$ is bipartite when the set $V (G)$ can be partitioned into two subsets $U$ and $W$ called partite sets such that every edge of $G$ joins a vertex of $U$ and a vertex of $W$

a nontrivial graph $G$ is bipartite if it doesn’t contain odd length cycles
a complete bipartite graph is a bipartite graph where each vertex of $U$ is adjacent to every vertex of $W$ , it’s denoted as $K_{∣ U ∣, ∣ W ∣}$
a star is a complete bipartite graph where $K_{1, ∣ W ∣}$ or $K_{∣ U ∣, 1}$

$k$ -partite graph

A graph $G$ is $k$ -partite when the set $V (G)$ can be partitioned into $k$ subsets $V_{1}, V_{2}, \dots, V_{k}$ such that every edge of $G$ joins a vertex of $U$ and a vertex of $W$

Biconnected graph

A biconnected graph $G$ is a connected and “nonseparable” graph meaning that if any vertex (and its incident edges) is removed the graph will remain connected, therefore a biconnected graph doesn’t have cut-vertices

Multigraphs

A multigraph $M$ is a graph where every two vertices of $M$ are joined by a finite number of edges, when two or more edges join the same pair of distinct vertices those edges are called parallel edges

Pseudographs

A pseudograph $P$ is a graph where an edge is allowed to join a vertex with itself, such an edge is called a loop

Weighted graph

Let $G$ be a multigraph, let’s replace all the parallel edges joining a particular pair of vertices by a single edge which is assigned a positive integer representing the number of parallel edges, this new representation is refered as a weighted graph

Digraphs

A directed graph $D$ is a finite nonempty set $V$ of vertices and a set $E$ of ordered pairs of distinct vertices, the elements of the set $E$ are called directed edges or arcs, arcs are represented with arrows instead of plain line segments

if $u v$ is a directed edge then $u$ is adjacent to $v$ and $v$ is adjacent from $u$

Degrees

The degree of a vertex $v$ is the number of edges incident with $v$ denoted by $d e g (v)$ (with loops counted twice)

the minimum degree of a graph $G$ is the minimum degree among all the vertices of $G$ denoted as $δ (G)$
the maximum degree of a graph $G$ is the maximum degree among all the vertices of $G$ denoted as $Δ (G)$
a vertex of degree $0$ is called an isolated vertex
a vertex of degree $1$ is called an end vertex (or leaf)
a vertex of even degree is called an even vertex
a vertex of odd degree is called an odd vertex
two vertices of $G$ that have the same degree are called regular vertices
if a graph $G$ has the same degree $r$ for all its vertices it’s called an r-regular graph

In a graph $G$ of $n$ vertices the following equality relation holds

0 \leq δ (G) \leq d e g (v) \leq Δ (G) \leq n - 1

First theorem of graph theory

if $G$ is a graph of size $m$ then

\sum_{v \in V (G)} d e g (v) = 2 m

When summing the degrees of $G$ each edge is counted twice

Degrees in a bipartite graph

Suppose that $G$ is a bipartite graph with two partite sets $U$ and $W$ , then

\sum_{u \in V (U)} d e g (u) = \sum_{w \in V (W)} d e g (w) = m

Corollary: every graph has an even number of odd vertices

Proof: Let $G$ be a graph of size $m$ , dividing $V (G)$ into two subsets $V_{e v e n}$ which consists of even vertices and $V_{o d d}$ which consists of odd vertices then by the first theorem of graph theory

\sum_{v \in V_{e v e n} (G)} d e g (v) + \sum_{v \in V_{o d d} (G)} d e g (v) = 2 m

the number $\sum_{v \in V_{e v e n} (G)} d e g (v)$ is even since it’s a sum of even numbers thus $\sum_{v \in V_{o d d} (G)} d e g (v)$ is also even and it can be even only if the number of odd vertices is even (a sum of two odd numbers gives an even number)

Degree sequences

A deIf the degrees of a graph $G$ are listed in a sequence $s$ then $s$ is called a sequence degree, e.g.

s : 4, 3, 2, 2, 2, 1, 1, 1, 0

Suppose we’re given a finite sequence $s$ of nonnegative integers, a well known problem is if we can build a graph out of this sequence, to solve this problem let’s talk about some facts

the degree of any vertice can never be greater than $n - 1$ where $n$ is the order of the graph
a graph has an even number of odd vertices

There’s a theorem called Havel-Hakimi which solves the problem above in polynomial time

A non-increasing sequence $s : d_{1}, d_{2}, \dots, d_{n}$ where $d_{1} \geq 1$ can form a graph only if the sequence

s_{1} : d_{2} - 1, d_{3} - 1, \dots, d_{d_{1} + 1} - 1, d_{d_{1} + 2}, \dots, d_{n}

forms a graph

According to this theorem we can create a new sequence based on the one above that is also a graph, we can apply the theorem recursively to test if the original sequence forms a graph

\begin{aligned} s_{1} & : 4, 3, 2, 2, 2, 1, 1, 1, 0 \\ s_{2} & : 2, 1, 1, 1, 1, 1, 1, 0 removing d_{1} = 4 and subtracting 1 from the following 4 elements \\ s_{3} & : 1, 1, 1, 1, 0 removing d_{1} = 2 and subtracting 1 from the following 2 elements \\ s_{4} & : 1, 1, 0 removing d_{1} = 1 and subtracting 1 from the following element \\ s_{5} & : 0 removing d_{1} = 1 and subtracting 1 from the following element \end{aligned}

bool graph_from_sequence(vector<int> &degrees) {
  int sum = 0;
  int size = degrees.size();
  for (int i = 0; i < size; i += 1) {
    sum += degrees[i];
    if (degrees[i] >= size || degrees[i] < 0) {
      // a vertice can have a maximum degree of n - 1
      // also none of the degrees can be negative
      return false;
    }
  }

  if (sum == 0) {
    // trivial case
    return true;
  }

  sort(degrees.begin(), degrees.end());

  // removing d_1
  int max_degree = degrees.back();
  degrees.pop_back();
  size -= 1;

  // subtracting 1 from the next d_1 elements
  for (int i = 0; i < max_degree; i += 1) {
    degrees[size - 1 - i] -= 1;
  }
  return graph_from_sequence(degrees);
}

Graphs and matrices

A graph can also be described using a matrix, the adjacency matrix of a graph $G$ of order $n$ and size $m$ is a $n \times n$ matrix $A = [a_{i j}]$ $where

a_{i j} = {\begin{cases} 1 & if v_{i} v_{j} \in G \\ 0 & otherwise \end{cases}

The incidence matrix of a graph $G$ of order $n$ and size $m$ is a $n \times m$ matrix $B = [b_{i j}]$ where

b_{i j} = {\begin{cases} 1 & if v_{i} is incident with e_{j} \\ 0 & otherwise \end{cases}

G = (V, E) V = {0, 1, 2, 3, 4} E = {{0, 1}, {0, 2}, {0, 3}, {1, 3}, {2, 3}, {3, 4}}

A = [\begin{matrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{matrix}] B = [\begin{matrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]

Useful observations

Let $A^{k}$ be the adjacency matrix of a graph $G$ raised to the $k$ -th power, the entry $a_{i j}^{(k)}$ is the number of distinct $v_{i} - v_{j}$ walks of length $k$ in $G$

Proof: assume for a positive integer $k$ that the number of $v_{i} - v_{j}$ walks of length $k$ is given by $a_{i j}^{(k)}$ in the matrix $A^{k}$ , then $A^{k + 1} = A^{k} \times A$ , now a cell $a_{i j}^{(k + 1)}$ is the dot product of row $i$ of $A^{k}$ and column $j$ of $A$

a_{i j}^{(k + 1)} = \sum_{t = 1}^{n} a_{i t}^{(k)} \cdot a_{t j}

The first element of this sum is the number of walks of length $k$ from $v_{i}$ to $v_{1}$ (stored in $a_{i 1}^{(k)}$ ) times the number of walks of length $1$ from $v_{1}$ to $v_{j}$ (stored in $a_{1 j}$ ), the second element follows the same formula but using $v_{2}$ as the vertex used to “join” the walks of length $k$ and $1$