Graph Theory - setting the ground

So after the introduction, it is now time to dive in to the theory itself. First, I am warning you, in this post I am going to present a lot of definitions, and I mean it, there will be a lot of it. However, this post is crucial in order to understand later posts, and that is because of a simple reason, I have to set the ground first before we can see start proving theorems, and develop the theory. OK, let’s begin!

Definitions overloading began

The very first definition I am going to state here, is of course, the definition of a Graph.

A Graph $G$ is an ordered pair $G=(V,E)$ where

$V$ is a non-empty set of Vertices (vertex in singular)
$E$ is a set of unordered pairs of elements of $V$ . i.e: $E\subseteq V\times V$ . The elements of $E$ are called Edges.

I will usually write $V(G)$ when I refer to the set of vertices, and $E(G)$ when I refer to the set of edges.

I lied a little bit up there, this definition is the definition of an Undirected Graph. If the pairs in $E$ were ordered pair, then we would get a Directed Graph. Let’s see an example:

In this example the set of vertices is $V=\{1,2,3,4\}$ , and the set of edges is $E=\{\{1,2\},\{1,3\},\{1,4\},\{1,5\}\}$ . Take a look at it carefully, try to match each edge on the drawing to the pair in the set of edges. Got it? good, let’s add more definitons:

An edge from a vertex to itself is called a loop. A multiple edge is an edge that appears in $E$ more than once.

This Graph Has Two loops at the vertex 1. Those loops are also both multiple edges, since their representation as a pair is $\{1,1\}$ .

A Simple Graph is a graph that has no loops and mutiple edges.

A Graph is finite is the set of vertices is finite. i.e $|V|<\infty$ .

Let that sink in, and make sure you understand these definitions before I continue, All good? Great! We are making progress, yet we have more to see.

For $G=(V,E)$ :

If $e\in E$ and $v\in e$ we say that $v$ is incident to $e$ , and $e$ is incident to $v$
if ${u,v}\in E$ we say that $u,v$ are adjacent / neighbors.
if $e_1\cap e_2 \neq \emptyset$ we say that $e_1, e_2$ are adjacent.
The Endpoints of an edge $e$ are the vertices incident to it.
an Isolated vertex is a vertex who is not incident to all the edges.

Here the blue vertex is incident both of the green vertices, which are adjacent to each other as well. The blue edges endpoints, are the blue vertex, and one of the green vertices. Once again, make sure you understand those definitions since I will use them a lot in the future.

In math, when defining a new structure, we always like to identify structures as the same, or more formally, we want to know when two structures are Isomorphic. In order to determine wheter two graphs are isomorphic or not we need a map between one graph to the other that preserves the first graph’s properties. Try to think of such a map.

Let’s define this map properly: Let $G_1=(V_1,E_1), G_2=(V_2,E_2)$ be two graphs. They are said to be isomorphic if there is a bijection (one-to-one & onto) $\varphi:V_1\to V_2$ such that:

\{u,v\}\in E_1 \Leftrightarrow \{\varphi(u),\varphi(v)\}\in E_2

What this map says that if there is an edge between two vertices in the first graph, then there will be an edge between the outputs of those vertices in the second graph. Another way to see it, is to realize that if such a map exits, then those two graphs are the same, they only differ by the name of the vertices.

That is a great and simple example of isomorphic graph, we can define a map $\varphi:V_1\to V_2$ :

$\varphi(1) = 1$
$\varphi(2) = 2$
$\varphi(3) = 4$
$\varphi(4) = 3$

You can check that this is indeed an isomorphism, and we can ‘move’ the vertices of the $G_2$ to get a graph that looks exactly like $G_1$ .

Can you see why those graphs are the same? If you do, thats great, you just won some more definitions! However, there is a twist, we are now going to bring matrices to our playground

Special matrices of a graph.

I am going to name the main two matrices used in graph theory, and they were the first to give a boost to a whole new topic: algebraic graph theory – a topic that I am not going to go into at this time.

The first matrix is called the incident matrix, it is denoted by $M(G)=(M_{v,e})_{v\in V,e\in E}$

The number of rows is the number of vertices, and the number of columns is the number of edges. each enrty in the matrix is defined by:

M_{v,e}=\begin{cases} 2 & e\text{ is a loop incident to }v\\ 1 & e\text{ is incident to }v\text{ but not a loop}\\ 0 & \text{else} \end{cases}

Lets see an example, consider the graph:

Then it’s incident matrix is:

\left(\begin{array}{cccccc} 1 & 2 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right)

Try fill the matrix yourself and see if you get the same result.

The second matrix is called the adjacency matrix. it is denoted by $A(G)$ . it is a square matrix which it’s entries are:

A_{i,j}=\begin{cases} 1 & \{i,j\}\in E\\ 0 & \{i,j\}\notin E \end{cases}

However, we count a loop twice – i.e if there is a loop at the $i^{th}$ vertex, the $ii$ entry is going to be 2. If there are more than 1 loop in the vertex, then for each loop – add two to the $ii$ entry. For example, in the graph above, the adjancey matrix is

\left(\begin{array}{ccccc} 4 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 \end{array}\right)

Those matrices give a lot of information about the graph, and we can study a graph from them (for example, the sum of the $i^{th}$ row / column is exactly the degree [that’s the next definition] of the $i^{th}$ vertex), but as I said before, this thing are done in algebraic graph theory, which I am not going to go into it here.

In case you feel like you need more definitions, I Won’t let you down

The Degree of a vertex, $d(v)$ is the number of edges incident to it, where you count a loop twice.

The Maximal Degree in a graph is denoted by $\Delta(G)$ , and the Minimal Degree in a graph is denoted by $\delta(G)$ .

I will also denote $e(G)=|E(G)|,v(G)=|V(G)|$ .

The First theorem

With all the definitions we are now ready to prove our first Theorem! it is called the Degree-Sum Formula. and The theorem states that in any Graph:

\sum_{v\in V}d(v)=2\cdot e(G)

The proof is super short:

Every edge increases the degrees of it’s endpoints by 1, meaning that for every edge added to the graph, we also increase the sum of the degrees by two.

You can also prove it using the incident matrix, if you notices, the sum of the entries of each column is two (that is because each edge has two endpoints [the endpoints can be the same]) so the total sum of the entries in the martix is $2\cdot e(G)$ . On the other hand, we can look at the sum of each row, the rows represent vertices, and the entry at the $i^{th}$ column indicates if the vertex is an endpoint, or not. Therefore, the sum of each row is the degree of the vertex, summing up all the rows to get the sum of all degrees. Compare both ways of summing the entries to get the formula.

This theorem is super simple but we can conclude two great statements:

In any graph, the sum of the degrees is even.
In any graph, the number of vertices of odd degree has to be even.

Try to explain yourself why it is true. And think about how simple this theorem is, and how it helped us to conclude pretty cool results!

Last round, I swear!

A Walk in a graph is a sequence of vertices and edges $v_0,e_1,v_1,e_2,v_2,\dots,e_l,v_l$ . Where the endpoints of $e_i$ are $v_{i-1},v_{i}$ .
A Trail is a walk with no repeated edges.
A Path is a walk with no repeated edges.
The Length of a walk is the number of edges in it.
The Distance between two vertices is the length of the shortest path between them, if there is no such path, the distance is defined to be $\infty$ .
A Circuit is a walk where $v_0=v_l$ .
A Cycle is a walk where no vertex is repeated (exept $v_0=v_l$ ).

Here there is a path between the red vertices (marked in green). This is indeed a path and a trail, since no edges & vertices are repeated.

This is an example of a walk which is not a path, since a vertex is repeated.

Two vertices are said to be Connected if there is a path between them
The Connected relation, is an equivalence relation, which divides the graph into Connected components
If the graph contains only one component it said to be Connected.

This graph has 2 components.

Summary

That is it! in the next post I am finally going to prove more theorems and develop the theory. I hope you survived it, see you in the next one!

Graph Theory – setting the ground

Definitions overloading began

Special matrices of a graph.

In case you feel like you need more definitions, I Won’t let you down

The First theorem

Last round, I swear!

Summary

Like this:

2 thoughts on “Graph Theory – setting the ground”

Leave a Reply Cancel reply

Definitions overloading began

Special matrices of a graph.

In case you feel like you need more definitions, I Won’t let you down

The First theorem

Last round, I swear!

Summary

Share

Like this:

2 thoughts on “Graph Theory – setting the ground”

Leave a Reply Cancel reply