Introduction to Graph Theory - Part 2

Now, let’s dive deeper and introduce the first key pieces of graph notation and explore how we can describe graphs mathematically. For the beginning, we will look at some basic definitions and observations. Note that these definitions and notation will be used throughout this article.

Basics

Before we start defining graphs, we need to introduce vertices and edges. A vertex is a point in the graph, and an edge is a connection between two vertices. In other words, an edge is a tuple of two vertices.

Now, a graph $G$ is a collection of vertices $V$ and edges $E$. We write $G = (V, E)$ to denote a graph with vertex set $V$ and edge set $E$. We formalize this in the following definition:

Definition 1. A graph is a pair $(V, E)$, where $V$ is a finite set, and $E$ is a subset of $P_2(V)$. The number of vertices is often abbreviated as $|V| = n$ and the number of edges as $|E| = m$.

To make things more clear, let's look at an example. Consider the following graph $G$ = $(\{1,2,3\}, \{(1,2), (1,3), (2,3)\})$. Here, $V = \{1,2,3\}$ and $E = \{(1,2), (1,3), (2,3)\}$. This can be visualized as three points and the edges between each pair of points, see the following figure:

Due to the definition above, we can see that the order of the vertices in an edge does not matter. Therefore, $(1,2)$ and $(2,1)$ are the same edge¹.

Due to their simplicity, graphs can be used to depict and model relationships and structures between objects - the objects under consideration become nodes, their relationship to an edge in between. Before we move on, let's look at a few more examples.

Let's consider a simple example. Suppose we have a group of 5 people and we want to model how they are related to each other. We can do this by representing each person as a vertex and drawing an edge between two vertices if the corresponding people are friends. This way, we can visually represent the relationships between the people in the group. This graph is called a friendship graph. As you surely noticed, the friendship between two people is mutually, i.e. if Alice is friends with Bob, then Bob is friends with Alice. This is an example of a undirected graph, where the edges have no direction².

In our small example, Alice and Bob are friends - thus, they are close to each other. As it nice for friends to be close, we say that they are adjacent. Even better, they live next to each other. We say that they are neighbors. We formalize this in the following definition:

Definition 2. Two vertices $v$ and $w$ are adjacent if there exists an edge $e = (v, w) \in E$. We say that the vertices $v$ and $w$ are neighbors if they are adjacent.

We continue with more definitions. Let's assume that the friendship graph is way bigger than the three people we considered before. We can now ask ourselves how many friends Alice has. This number is called the degree of the vertex $v$. Formally, we define the degree of a vertex $v$ as follows:

Definition 3. The degree of a vertex $v$ is the number of vertices adjacent to $v$, denoted by $d(v)$.

Consider the following example. We have a graph $G = (\{1,2,3,4,5\}, \{(1,2), (1,3), (2,3), (3,4), (4,5)\})$. The degrees of the vertices are $d(1) = 2$, $d(2) = 2$, $d(3) = 3$, $d(4) = 2$, and $d(5) = 1$.

When looking at the degree of the vertices, we obtain the following small observation:

Observation 1. The degree of a vertex is a number between $0$ and $n-1$, where $n$ is the number of vertices in the graph.

This observation might look trivial, but will be the first proved result in this series.

Proof. We know that the degree of a vertex is the number of vertices adjacent to it. Since there are $n$ vertices in the graph, the degree of a vertex is at most $n-1$. Since the degree of a vertex is a non-negative integer, the degree of a vertex is at least $0$.

In other words, the degree of a vertex is the number of neighbors it has.