Graph Theory

Fundamentals for Modeling Networks and Relationships

KT14403 DISCRETE STRUCTURE

 What is a Graph?

Formal Definition Graph Visualization

A graph G = (V, E) consists of:

V: A set of vertices (nodes)

E: A set of edges (connections between vertices)
V1 e1 V2
G = (V, E) where V ≠ ∅
Vertex 1 Vertex 2
e2

Vertices (V): Represent Edges (E): Represent

entities or objects relationships e3 V3 e6

e4
Vertex 3
Directed: Edges have Undirected: Edges are
direction (u → v) bidirectional
V4 e5 V5

Key Concepts Vertex 4 Vertex 5

Adjacent vertices: Two vertices connected by an edge Incident edge: An

edge that connects to a vertex Loop: An edge that starts and ends at the
same vertex Parallel edges: Multiple edges between the same pair of Vertices (V) Edges (E)
vertices
 Types of Graphs

Different Types of Graph Structures

Simple Graph Directed Graph Weighted Graph

Undirected, no loops Edges have direction Edges have weights

A simple graph has no loops and no parallel edges. A directed graph (digraph) has edges with A weighted graph assigns a weight (cost, distance,
Each edge connects two distinct vertices without direction. Each edge is an ordered pair (u, v). time) to each edge.
direction.
Edges have direction Edge weights represent cost
No self-loops allowed Represented as arcs Used in shortest path algorithms
No parallel edges Asymmetric relationships Non-negative values
Undirected connections
 Degree of a Vertex

Definition & Computation

Degree Example
The degree of a vertex v, denoted deg(v) or d(v), is the number of
edges incident with v. Each loop contributes 2 to the degree.

deg(A) = 3 (connected to B, C, D via e1, e2, e3) A e1 B

deg(B) = 2 (connected to A, C via e1, e4)
deg(A)=3 deg(B)=2
deg(C) = 2 (connected to A, B via e2, e4)
e3 e2 e4
deg(D) = 1 (connected to A via e3)

D C
Isolated Vertex: Loop:
deg(D)=1 deg(C)=2
deg(v) = 0 Contributes 2 to degree

E
Handshaking Lemma
deg(E)=0

Sum of all degrees = 2 × |E| The sum of degrees of all vertices

equals twice the number of edges. Corollary: The number of odd- Regular Vertex Isolated Vertex
degree vertices is always even.
 Paths and Circuits

Path Definitions
Path and Circuit Visualization
Path: A sequence of distinct vertices where consecutive vertices are
joined by edges
Simple Path: A path with no repeated vertices or edges
Circuit/Cycle: A closed path that starts and ends at the same vertex

e1 e2
U V W
Path: Sequence of vertices Simple Path: No repeated
connected by edges vertices or edges Start Path End
e3 e5

Circuit: Closed path, starts Cycle: Circuit with no

and ends at same vertex repeated vertices e4
Y X

Circuit Circuit

Key Concepts

Example: Path U → V → W is a simple path

Example: Circuit V → W → X - Y → V is a cycle
Note: A cycle has no repeated vertices except the starting/ending
Vertices Edges Path (Green) Circuit (Orange)
vertex
 Walks and Trails

 Walk Definitions  Trail Definitions

A walk is a finite sequence of alternating vertices and edges: A trail is a walk in which all edges are distinct.
v₀, e₁, v₁, e₂, ..., eₙ, vₙ
In a trail, you are not allowed to traverse the same edge more
It begins at starting vertex v₀ and ends at terminal vertex vₙ. In than once. However, vertices may be repeated. Every trail is a
a walk, both vertices and edges may be repeated. walk, but not every walk is a trail.

 Open Walk  Open Trail

The starting and ending vertices are different. A trail where the starting and ending vertices are different.
v₀ ≠ vₙ No edges are repeated anywhere.

 Closed Walk  Closed Trail

The starting and ending vertices are the same. A trail where the starting and ending vertices are the same.
v₀ = vₙ Note: A closed trail is also commonly called a Circuit.

Example: A sequence u → v → w → v → x is a valid open walk Example: u → v → w → u is a closed trail (circuit) assuming it only
(vertex v and potentially an edge is repeated). uses distinct edges to form the loop.
 Paths, Circuits, and Cycles

 Path Definitions  Concept Hierarchy Flow

A path is an open trail in which no vertex is repeated.
WALK
Any alternating sequence of vertices & edges
Open Path Closed Path
Starts & ends at different vertices. Zero Starts & ends at the same vertex. No other 
repeated vertices. repeated vertices.
TRAIL
A walk with no repeated edges


 Circuit
PATH
A circuit is a closed trail. It starts and ends at the same vertex, and has no A trail with no repeated vertices
repeated edges.
 
Key Point: In a circuit, vertices CAN be visited more than once, as long as no edge is
traversed twice. CIRCUIT CYCLE
Closed Trail Closed Path

 Cycle  Example Analysis

A cycle is a circuit in which no vertex is repeated (except for the starting and v₁→v₂→v₃→v₁ This is a Cycle (and a circuit). No edges or vertices are
ending vertex). repeated, starts and ends at v₁.

Rule of thumb: Every cycle is a circuit, but not every circuit is a cycle. v₁→v₂→v₃→v₂→v₁ This is a Closed Walk. It is NOT a circuit or cycle because
edge {v₁,v₂} and {v₂,v₃} are traversed twice.
 Euler and Hamiltonian Graphs

Euler Circuits Hamiltonian Cycles

An Euler circuit is a closed trail that uses every edge exactly once. A A Hamiltonian cycle is a cycle that visits every vertex exactly once.
graph has an Euler circuit if and only if it is connected and every vertex Unlike Euler circuits, there is no simple necessary and sufficient
has even degree. condition.

Condition: All vertices have even degree Condition: Visits every vertex exactly once

Edges: Uses every edge exactly once Vertices: Visits each vertex once

Return: Returns to starting vertex Return: Returns to starting vertex

Euler Trail (Open) Hamiltonian Path

An Euler trail exists if exactly two vertices have odd degree. It starts A Hamiltonian path visits every vertex exactly once but does not need
and ends at different vertices. to return to the start.
 Euler Circuit Example

Detailed Explanation Euler Circuit Diagram

Graph Properties:

This is a connected graph.

Each vertex has an even degree.
Hence, this graph has an Euler circuit.

The Complete Euler Circuit Path:

(v1, e1, v2, e2, v3, e3, v4, e4, v6, e5, v2, e6,
v4, e7, v5, e8, v1)

This path is a valid circuit because it contains all vertices and

traverses all edges of G exactly once, starting and ending at the
same vertex.
 Hamiltonian Path Example

Path Analysis Graph Visualization

We can see that once we travel to vertex E

there is no way to leave without returning to C,
so there is no possibility of a Hamiltonian
circuit.

If we start at vertex E we can find several

Hamiltonian paths, such as ECDAB and
ECABD.
 Adjacency Matrices

Definition & Properties

Graph Visualization
An adjacency matrix A for a graph with n vertices is an n×n matrix
where A[i,j] = 1 if there is an edge from vertex i to vertex j, and 0
otherwise.

Example: 3-vertex graph Vertices: {v1, v2, v3} e1

v1 v2
v1 v2 v3
Vertex 1 Vertex 2
v1 0 1 1

v2 1 0 1 e2 e3

v3 1 1 0

v3
Symmetric: A[i,j] = A[j,i] for A^k[i,j] = number of walks of
undirected graphs length k from vi to vj Vertex 3

Key Properties

Diagonal: A[i,i] = 0 (no self-loops in simple graphs)

Vertices Edges
Sum of row i: Out-degree of vertex vi
Sum of column j: In-degree of vertex vj
Adjacency Matrix Example 1

Graph with 6 Vertices Corresponding 6x6 Adjacency Matrix

Observations:
• The matrix is symmetric because the graph is undirected.
• The main diagonal contains only 0s because there are no loops.
 Adjacency Matrix Example 2

Graph Visualization Matrix Representation

Parallel Edges & Loops in Matrices:

• Parallel Edges: Notice A[1,2] = A[2,1] = 2 because there are two edges (e1 and e2) between v1 and v2.
• Loops: Notice A[4,4] = 1 because there is one loop (e6) at vertex v4.
 Weighted Graph Example

Concept & Application Graph Visualization

The edges connecting two vertices can be assigned a

nonnegative real number, called the weight of the
edge.

If the graph represent a highway structure, the weight

can represent the distance between two places, or
the travel time from one place to another.

Weighted graphs form the basis for many

optimization algorithms, such as finding the shortest
path (e.g., Dijkstra's Algorithm).
 Shortest Path Algorithms

 Dijkstra's Algorithm Steps  Weighted Graph with Shortest Path

1 Initialize
Set source distance to 0, all others to ∞. Mark all nodes as
unvisited.

2 1
A B C
2 Select Minimum
Select unvisited node with smallest tentative distance. Start 2 5
4
3

3 Relax Edges
D E
Update distances to neighbors if a shorter path is found.
2

4 End

4 Mark Visited
Mark current node as visited and repeat until all nodes are visited.

Time Complexity: O(n²) with arrays, O((n + m) log n) with priority

Start Node End Node Shortest Path Other Edges
queue
Space Complexity: O(n) for distance array