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\))

\[ G = (V, E) \\ V = \{1, 2, 3, 4, 5, 6, 7\} \\ E = \{ \{1, 5\}, \{5, 7\}, \{2, 3\}, \{2, 4\}, \{3, 4\} \} \]

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\)