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{align*} G &= (V, E) \\ V &= \{1, 2, 3, 4, 5, 6, 7\} \\ E &= \{ \{1, 5\}, \{5, 7\}, \{2, 3\}, \{2, 4\}, \{3, 4\} \} \end{align*} $$

Properties

  • the order of a graph is the number of vertices (written as $\mid G \mid$)
  • the size of a graph is the number of edges (written as $\Vert G \Vert$)
  • an edge ${u, v}$ is usually written as $uv$ (or $vu$), if $uv$ 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 = \varnothing$ 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 = uv \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, \ldots, 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} = \tfrac{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, $uv \in E(\bar{G})$ and $uv \not\in 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_{\mid U \mid, \mid W \mid}$
  • a star is a complete bipartite graph where $K_{1, \mid W \mid}$ or $K_{\mid U \mid, 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, \ldots, 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 $uv$ 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 $deg(v)$ (with loops counted twice)

  • the minimum degree of a graph $G$ is the minimum degree among all the vertices of $G$ denoted as $\delta(G)$
  • the maximum degree of a graph $G$ is the maximum degree among all the vertices of $G$ denoted as $\Delta(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 \delta(G) \leq deg(v) \leq \Delta(G) \leq n - 1 $$

First theorem of graph theory

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

$$ \sum_{v \in V(G)} deg(v) = 2m $$

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)}deg(u) = \sum_{w \in V(W)} deg(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_{even}$ which consists of even vertices and $V_{odd}$ which consists of odd vertices then by the first theorem of graph theory

$$ \sum_{v \in V_{even}(G)} deg(v) + \sum_{v \in V_{odd}(G)} deg(v) = 2m $$

the number $\sum_{v \in V_{even}(G)} deg(v)$ is even since it’s a sum of even numbers thus $\sum_{v \in V_{odd}(G)} deg(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, \ldots, d_n$ where $d_1 \geq 1$ can form a graph only if the sequence

$$ s_1: d_2 - 1, d_3 - 1, \ldots, d_{d_1 + 1} - 1, d_{d_1 + 2}, \ldots, 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{align*} s_1 &: 4, 3, 2, 2, 2, 1, 1, 1, 0 \\ s_2 &: 2, 1, 1, 1, 1, 1, 1, 0 \quad \text{removing $d_1 = 4$ and subtracting $1$ from the following $4$ elements} \\ s_3 &: 1, 1, 1, 1, 0 \quad \text{removing $d_1 = 2$ and subtracting $1$ from the following $2$ elements} \\ s_4 &: 1, 1, 0 \quad \text{removing $d_1 = 1$ and subtracting $1$ from the following element} \\ s_5 &: 0 \quad \text{removing $d_1 = 1$ and subtracting $1$ from the following element} \end{align*} $$
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_{ij}]$ $where

$$ a_{ij} = \begin{cases} 1 & \text{if $v_iv_j \in G$} \\ 0 & \text{otherwise} \end{cases} $$

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

$$ b_{ij} = \begin{cases} 1 & \text{if $v_i$ is incident with $e_j$} \\ 0 & \text{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{bmatrix} 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{bmatrix} \quad B = \begin{bmatrix} 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{bmatrix} $$

Useful observations

Let $A^k$ be the adjacency matrix of a graph $G$ raised to the $k$-th power, the entry $a_{ij}^{(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_{ij}^{(k)}$ in the matrix $A^k$, then $A^{k + 1} = A^k \times A$, now a cell $a_{ij}^{(k + 1)}$ is the dot product of row $i$ of $A^k$ and column $j$ of $A$

$$ a_{ij}^{(k + 1)} = \sum_{t=1}^n a_{it}^{(k)} \cdot a_{tj} $$

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