Graph Theory 101

an introduction to graph theory

Graph theory is a field of discrete mathematics, discrete in the sense that the structures we deal with are distinct and are not subject to properties of closeness such as continuity.Graph theory is one of the notable branches in mathematics.It can be used to model different kinds of problems and is also one of the fields with the most open problems.

In this series of posts I will give a technical exposition to graph theory, discuss few ideas and also show you a parable about proofs in mathematics. For the first post I will give an exposition of graphs as objects and discuss some representations. I will then discuss the usage of graphs as data structures. In the next posts I will try to branch into algorithms and applications of graphs to some problems.

Why Graph Theory

Graph theory is useful in modeling a lot of problems we face IRL such as how to effectively deliver 4 food orders around town, or how to select the best combinations to break a pin code or how to effectively arbitrage between currencies (triangular arbitrage) … Graphs became important as tools to solve such problems. The most remarkable one, also being foundational in topology and graph theory is Euler’s Konisberg Problem

Here’s how one might represent this problem using graphs which might seem more intuitive :

You can read more about Euler’s proof.

What is a graph ?

A graph, mathematically, is an ordered pair of sets $(V,E)$ the first is the set of vertices also called nodes it has to be non-empty.The second is a collection of pairs called edges. Edges are a two element subsets of V, meaning that each element of E is a pair of elements in V. An edge represents the link between two vertices in a graph.

\[ G=(V,E) |\ V = \{ v_1,v_2,v_3…,v_n \} \ | E = \{e_k\}_k \in \{1,..,n\}, e_k = \{\{ v_i,v_j \}\} \ (i, j) \in \mathbb{N}\]

So, $ E $ is a set of pairs $ {e_k} $ denotes an element of E where $ \mathit{k} $ is an index. An edge is thus an un(ordered) pair of vertices, if the Graph is directed which we’ll call a digraph then the pair is ordered and \[ (v_i,v_j) \neq (v_j,v_i) \]

Visually digraph’s edges have arrows that denote the origin and destination of the edge respectively.

A Graph is also this (visually): complexer

A directed graph : digraph mdigraph

You should think of Graphs as just mathematical objects with certain nice properties. Trees such as binary trees are also graphs since every tree can be written as a set of vertices and edges. We will look at trees sometime later but for now I hope the idea of what is a graph is now clear.

Edges can be loops as well such as in the example below in the test your understanding section .

There’s no requirements for graphs to have edges, in case where a graph has no edges each vertex is said to be isolated.

Properties and terminology

Adjacency : $(v_i,v_j)$ a pair of vertices is said to be adjacent if it belongs to E meaning there’s an edge betwen them.
Neighbors : For each element $v_i$ of $V$ we can take a subset of $V$,it’s neighbors noted as $\mathit{A(v)}$ such as for each $ v_k \, in \, \mathit{A(v_i)}$ we have $ (v_i,v_k) \in E $
Subgraphs : If $ G(V,E) $ is a graph and we take $ V’ \subset V $ and $ E’ \subset E $ then we can define $ G’(V’,E’) $ as a proper subgraph of $ G $, in the case where $ V’ = V $ then $ G’ $ is said to span $ G $
Degree : A vertex $ v_j $ is said to have $ k$-degrees if it’s connected to $k$-vertices if $G$ is directed (digraph) then we separate it’s degrees to two in-degrees and out-degrees , in-degrees are the number of edges ending in $v_j$ , out-degrees is the number of edges originating in $v_j$

P.S : In the case of a graph a loop adds 2 to the degree because each one can be seen as an adjacent vertex, in the case of a digraph a loop adds 1 to the in-degree and 1 to the out-degree.

Another property of graphs, as a theorem states :

\[2|E| = \sum_{i=1}^{n}deg(v_i) \]

Where $|E|$ denotes the Cardinal of $E$ (number of elements of the set)

Proof : The degree of a vertex represents to how many other vertices it’s connected to.Thus since every edge connects two vertices by summing over the degrees we end up counting each edge twice, for example if we have $ e = \{v_1,v_2\} $ then the sum of degrees will be …

Test your understanding

Consider the examples below :

Draw a graph G given $ V = \{u,v,w,x,y,z\} $ and $ E = \{\{u,v\},\{u,w\},\{u,x\},\{v,x\},\{x,y\},\{y,z\},\{z,w\}\} $
Given the following Graph give the sets $V$ and $E$

Moving around graphs

Given a graph $G(V,E)$ we define a path as a sequence of vertices $\{v_1,v_2,…,v_n\} $ such as $ \{v_k,v_{k+1} \} \in E : k \in \{1,..,n-1\} $

Paths are said to be simple if they don’t have loops or repeated edges, a path is said to be a cycle if it goes back to where it start i.e $ v_0 = v_n $

Paths will be the subject of most our graph problems finding short paths,or whether paths or cycles do exists are concrete problems you’ll often meet in coding problems.

Path 1 : $ (4,0,2,4,5) $ is not a simple path because $(4,2)$ was included twice
Path 2 : $ (1,4,0,5,1) $ is a cycle

Connectivity

Graphs are said to be connected if for every pair $ (u,v) : u \neq v $ there’s at least a path between them.

A very connected graph!

Graphs can have isolated nodes but you’ll rarely find those since they’re not as interesting as the others.

References

Some extra refrences :