Introduction Graph

What is a graph

A graph $G$ consists of:

Set $V$ of vertices (nodes)
Set $E$ of edges (where every edge connects two vertices) We write $G = (V, E)$

Multigraphs

flowchart LR
    A --- D
    A --- C
    A --- B
    D --- B
    C --- B
    D --- A
    C --- A

If there is more than one edge between two of the vertices, or a loop connecting a vertex with itself, we say that it is a multigraph
Two vertices that are connected by an edge are said to be adjacent

Walks, Trails and Paths

A walk from a vertex $u$ to a vetex $v$ is defined as:

An alternating sequence $u_1e_1y_2e_2u_3…,u_pe_pu_{p+1}$
Where $u_i$ are vertices, $e_j$ edges, $u = u_1$, $v = u_{p + 1}$
Endpoints of $e_i$ are $u_i$ and $u_{i+1}$

A trail is a walk in which all edges are distinct
A path is a walk in which all vertices are distinct

Examples

graph LR
    A ---|1| B
    A ---|3| E
    A ---|8| C
    B ---|2| D
    C ---|7| E
    C ---|9| F
    D ---|4| E
    D ---|5| F
    E ---|6| F

a1b1a3e7c is a walk
a3e7c8a1b2d is a trail
a1b2d4e7c is a path

Eulerian Trails

A Eulerian Trail (Or Eulerian path) in a graph is a trail that uses all the edges exactly once
The number of edges incident (attached) to a vertex is called the degree of a vertex.

For example:

flowchart LR
    A --- D
    A --- C
    A --- B
    D --- B
    C --- B
    D --- A
    C --- A

A has a degree of 5
B, C, and D have degrees of 3

A connected graph has an Eulerian trail if and only if either all its vertices have an even degree or exactly two of its vertices have an odd degree

Weighted Graphs

flowchart LR
    A ---|7|B
    A ---|5|C
    A ---|3|D
    B ---|2|D
    B ---|5|E
    C ---|11|D
    C ---|2|E
    D ---|4|E

A weighted grpah is a graph together with a function that assigns a number (called weight/cost) to every edge.
A graph $H = (V’, E’)$ is a subgraph of $G = (V, E)$ if:

$V’ \subseteq V$ (all vertices of $H$ are vertices of $G$)
$E’ \subseteq E$ (all edges of $H$ are edges of $G$)

Spanning Subgraph

flowchart LR
    A ---|7|B
    A ---|5|C
    A ---|3|D
    C ---|11|D
    C ---|2|E

A subgraph $H = (V’, E’)$ is a spanning subgraph of a graph $G = (V, E)$ if $V’ = V$ (all vertices of $H$ are vertices of $G$)

Connected Graphs

A graph $G = (V, E)$ is conected if:

There is a walk between every pair of vertices

Connected Example

flowchart LR
    A --- B
    B --- C
    A --- C
    C --- D
    D --- E
    E --- F
    F --- G
    G --- E

Disconnected Example

flowchart LR
    A --- B
    B --- C
    A --- C
    C --- D
    E --- F
    F --- G
    G --- E

(this graph is disconnected as you cannot walk from A to E)

Minimum Spanning Trees

Given graph $G = (V, E)$ and edge weights/costs $w(e)$
Find a connected spanning subgraph of the minimum total cost
The total cost of a subgraph is the sum of the edges of the subgraph

Prim’s Algorihtm

Two disjoint connected subgraphs are connected by the cheapest edge
It doesn’t matter which cheapest edge if multiple cheapest edges exist

Start at any node and mark it
Select a cheapest non-marked edge that connects a marked node to an unmarked node, and mark both that edge and the other endpoint
Repeat step 2 until all nodes are marked
The marked vertices and edges are a shortest spanning subgraph

flowchart LR
    A ---|7| B
    A ---|5| C
    A ---|3| D
    B ---|5| E
    B ---|2| D
    C ---|11| D
    C ---|2| E
    D ---|4| E

Step	Marked Edges	Marked Vertices
0		`A`
1	`AD`	`A, D`
2	`AD, DB`	`A, D, B`
3	`AD, DB, DE`	`A, D, B, E`
4	`AD, DB, DE, CE`	`A, D, B, E, C`

Cycles

A cycle in a graph is a non-empty trail from a vertex to itself in which no vertex is used more than once

flowchart LR
    A ---|7| B
    A ---|5| C
    A ---|3| D
    B ---|5| E
    B ---|2| D
    C ---|11| D
    C ---|2| E
    D ---|4| E

abdca is a cycle in the above graph

A loop in a graph is an edge from a vertex to itself

Detecting Cycles

If a graph has two different trails connecting two of its vertices, then a cycle is present

Trees

A tree is a connected graph with no cycles

For any tree $G$ with $n$ vertices

There is exactly one trail between any pair of vertices
$G$ is connected with $n - 1$ edges
$G$ is connected and either $n = 1$ and $G$ has no edges, or $n \geq 2$ and removing any edge makes $G$ disconnected
$G$ has no cycles and adding an edge between any two vertices creates a cycle containing them

Tree

flowchart TD
    A --- B
    B --- C
    B --- D
    C --- E

Not a Tree

flowchart LR
    A --- B
    B --- C
    A --- C
    C --- D
    E --- F
    F --- G
    G --- E

flowchart LR
    A --- B
    B --- C
    A --- C
    C --- D
    D --- E
    E --- F
    F --- G
    G --- E

Trees are cheap!

Let $G$ be a connected graph.
Every connected spanning subraph of $G$ with minimal total weight is a tree.

Proof: Let $H$ be a minimum connected spanning subgraph of graph $G$ with $n$ vertices

If $n = 1$ then the unique vertex of $G$ has a cost of $0$, it is a tree and spans $G$
If $n \geq 2$, removing any edge from $H$ disconnects it (it is cheapest) and by property 3, $H$ is a tree

Rooted Trees

A rooted tree is one that has a distinguished vertex (called the root) from which there is a path to any other vertex.
The height of a rooted tree is the length of its longest path.

flowchart
    0["org.kindlemodding.examplerepo
com.kindlemodding.examplepackage
1.2.3"]
    0 --- 1
    0 --- 13
    0 --- 3
    0 --- 7
    1(["org.kindlemodding.examplerepo
io.github.niluje.fbink
0.6.10 to 0.7.0"])
    1 --- 12
    1 --- 11
    1 --- 2
    2["org.kindlemodding.examplerepo
io.github.niluje.fbink
0.6.10"]
    2 --- 3
    2 --- 7
    3(["
testmax
0.0.0 to 1.0.0"])
    3 --- 4
    3 --- 5
    3 --- 6
    4["org.kindlemodding.examplerepo
testmax
0.99.99"]
    5["org.kindlemodding.examplerepo
testmax
0.2.3"]
    6["org.kindlemodding.examplerepo
testmax
0.1.2"]
    7(["
testmin
1.0.0 to 4294967295.4294967295.4294967295"])
    7 --- 8
    7 --- 9
    7 --- 10
    8["org.kindlemodding.examplerepo
testmin
1.999.999"]
    9["org.kindlemodding.examplerepo
testmin
1.1.1"]
    10["org.kindlemodding.examplerepo
testmin
1.0.0"]
    11["org.kindlemodding.examplerepo
io.github.niluje.fbink
0.6.11"]
    11 --- 3
    11 --- 7
    12["org.kindlemodding.examplerepo
io.github.niluje.fbink
0.6.99"]
    12 --- 3
    12 --- 7
    13(["
org.lua
0.0.0 to 4294967295.4294967295.4294967295"])
    13 --- 14
    13 --- 16
    13 --- 18
    14["org.kindlemodding.examplerepo
org.lua
9.2.3"]
    14 --- 15
    15(["
testmin
1.0.1 to 1.9.0"])
    15 --- 9
    16["org.kindlemodding.examplerepo
org.lua
4.5.6"]
    16 --- 17
    17(["
testmin
1.9.0 to 2.0.0"])
    17 --- 8
    18["org.kindlemodding.examplerepo
org.lua
1.2.5"]
    18 --- 15

Directed Graphs

A directed graph or a digraph is a set of vertices and a set of directed arrows where each arrow has a source and a target vertex

flowchart LR
    A --> B
    B --> C
    C --> D
    C --> F
    C --> E
    E --> F
    F --> A

If there is an arrow from $a$ to $b$

$a$ is a predecessor of $b$
$b$ is a successor of $a$

A directed walk form a vertex $a$ to a vertex $b$ in a digraph is a sequence of arrows starting in $a$ and ending in $b$ such that, for any two consecutive arrows in the sequence, the target of the first arrow is the source of the second.

A directed trail is a directed walk in which no edge is used more than once
A directed path is a directed walk in which no vertex is used more than once
A directed cycle in a digraph is a non-empty (directed) trail from a vertex to itself in which no vertex is used more than once

Underlying Graphs

flowchart LR
    A --- B
    B --- C
    C --- D
    C --- F
    C --- E
    E --- F
    F --- A

The underlying graph of a digraph can be obtained by replacing the arrows with undirected edges.
A digraph is connected if its underlying graph is connected

Introduction Graph

November 2025

What is a graph

Multigraphs

Walks, Trails and Paths

Examples

Eulerian Trails

Weighted Graphs

Spanning Subgraph

Connected Graphs

Connected Example

Disconnected Example

Minimum Spanning Trees

Prim’s Algorihtm

Cycles

Detecting Cycles

Trees

Tree

Not a Tree

Trees are cheap!

Rooted Trees

Directed Graphs

Underlying Graphs