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

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$

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

**First theorem of graph theory**

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

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

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

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.

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

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

```
bool graph_from_sequence(vector<int> °rees) {
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

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

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

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$