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** is an ordered pair where

- is a non-empty set of
**Vertices**(vertex in singular) - is a set of unordered pairs of elements of . i.e: . The elements of are called
**Edges**.

I will usually write when I refer to the set of vertices, and 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 were ordered pair, then we would get a **Directed Graph**. Let’s see an example:

In this example the set of vertices is , and the set of edges is . 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 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 .

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 .

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 :

- If and we say that is
**incident**to , and is**incident**to - if we say that are
**adjacent**/**neighbors**. - if we say that are
**adjacent**. - The
**Endpoints**of an edge 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 be two graphs. They are said to be **isomorphic** if there is a bijection (one-to-one & onto) 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 :

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

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

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 . 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 vertex, the entry is going to be 2. If there are more than 1 loop in the vertex, then for each loop – add two to the 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 row / column is exactly the degree [that’s the next definition] of the 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, is the number of edges incident to it, where you count a loop twice.

The **Maximal Degree** in a graph is denoted by , and the **Minimal Degree** in a graph is denoted by .

I will also denote .

## 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 . On the other hand, we can look at the sum of each row, the rows represent vertices, and the entry at the 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 . Where the endpoints of are . - 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 . - A
**Circuit**is a walk where . - A
**Cycle**is a walk where no vertex is repeated (exept ).

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!

## 2 thoughts on “Graph Theory – setting the ground”