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$$