Introduction to Graphs

Graph theory was founded in the 18th century, with Euler’s article on the Seven Bridges of Königsberg problem. The city of Königsberg had seven bridges, connecting the north and south banks of the river, and two fluvial islands (Kneiphof and Lomse). Back then, Königsberg looked roughly like this:

---
config:
  layout: elk
  look: handDrawn
---
graph LR
    N[North Bank]
    K[Kneiphof Island]
    L[Lomse Island]
    S[South Bank]

    N === K
    N === K
    N === L
    S === L
    S === K
    S === K
    K === L
North Bank
Kneiphof Island
Lomse Island
South Bank

The problem was to find a path such that a walker would cross each bridge exactly once. To solve this problem (by proving it had no solution), Euler found two useful abstractions: vertices representing land masses, and edges representing bridges. A key insight of framing the problem like this was that a graph can be represented in many ways (e.g., where to position the vertices), and all of them are equivalent.

In the 21st century, we define graphs as sets of objects (vertices) and pairwise relations between them (edges). Graphs are also known as networks; vertices as nodes; and edges as links. Königsberg is a graph with 4 vertices and 6 edges. Importantly, graphs represent similarities between objects. In maths, equivalence formalize the notion than objects can have a relationship of “sameness”. An equivalence relation is a binary relation that is reflexive, transitive and symmetric. It is noted like . The epitome of equivalence relation is “is equal to”. For instance, 2=42=2ππ. “Is greater than” is an example of non-equivalence, since it does not meet the symmetric property (e.g., 2>1 does not imply that 1>2). Since edges in a graph also capture this notion of “sameness” in some sense, they are tighly connected to equivalences: uv implies that there is a path between vertices u and v. Equivalently, u and v are in the same component.

Importantly, graphs are mathematical objects. A graph G can be defined as

G=(V,E)

Where V denotes the set of vertices and E the set of edges (pairs of vertices).

Notation note: V and E above refer sets, specifically to the vertex and edge set of a specific graph (G). Note that they are in italics. In contrast, the V in V(H) and V(I) refer to the vertex sets of graphs H and I respectively. Note that they are not in italics. I will follow the same convention elsewhere, e.g. when writing about graph’s matrices.

This notation allows to concisely define multiple types of graph:

  • Undirected graph: E{{u,v}u,vV}, i.e., the edges do not have directions.

    ---
    config:
    layout: elk
    look: handDrawn
    ---
    graph LR
    
        vertex_a((a))
        vertex_b((b))
        vertex_c((c))
    
        vertex_a === vertex_b
        vertex_a === vertex_c
        vertex_b === vertex_c
    
    a
    b
    c
  • Directed graphs: E{(u,v)u,vV}, i.e., the edges have directions.

    ---
    config:
    layout: elk
    look: handDrawn
    ---
    graph LR
    
        vertex_a((a))
        vertex_b((b))
        vertex_c((c))
    
        vertex_a --> vertex_b
        vertex_a --> vertex_c
        vertex_b --> vertex_c
    
    a
    b
    c

Sometimes, graphs are defined as triples. An example are multigraphs, graphs in which multiple edges between the same pair of vertices are allowed. They are triples G=(V,E,ϕ) in which the incidence function ϕ represents the mapping from edges to pairs of vertices. Königsberg is an example of multigraph, since it has multiple bridges connecting the same landmasses (e.g., the North Bank and the Kneiphof Island). For instance, the Königsberg graph is an undirected multigraph with:

V={N,K,L,S} E={e1,e2,e3,e4,e5,e6,e7} ϕ(x)={{N,K}if x=e1{N,K}if x=e2{N,L}if x=e3{S,L}if x=e4{S,K}if x=e5{S,K}if x=e6{K,L}if x=e7

Another type of graph that requires a triple are weighted graphs, in which each edge has a weight. They are triples G=(V,E,w) in which w is a function that maps edges to their weights. Note that weighted multigraph would be a quadruple, since it would require both an incidence and a weight functions.

Note: unless specified otherwise, in this series I will focus on simple graphs, which have at most one edge between any pair of vertices and no loops.

Further reading