Graph Theory

ℹ️ Why It Matters

Graphs model relationships between entities. Social networks (people as vertices, friendships as edges), knowledge graphs (concepts and their connections), molecular structures (atoms and bonds), and neural network architectures (layers and connections) are all graphs. Graph algorithms power GPS routing, search engines, recommendation systems, and network security. Understanding graph theory is essential for algorithm design, network analysis, and combinatorial optimization in computer science and AI.

Definitions

DfGraph

A graph is an ordered pair $G = (V, E)$ where $V$ is a finite set of vertices (nodes) and $E$ is a set of edges connecting pairs of vertices. An edge between vertices $u$ and $v$ is denoted $\{u, v\}$ or $(u, v)$ for directed graphs.

DfDirected Graph (Digraph)

A directed graph $G = (V, E)$ has edges with direction. Each edge is an ordered pair $(u, v)$ meaning there is a connection from $u$ to $v$ , but not necessarily from $v$ to $u$ .

DfWeighted Graph

A weighted graph assigns a numerical weight $w(e)$ to each edge $e \in E$ . Weights represent costs, distances, capacities, or probabilities depending on the application.

DfDegree

The degree of a vertex $v$ , denoted $\deg(v)$ , is the number of edges incident to it. In directed graphs, the in-degree $\deg^-(v)$ counts incoming edges and the out-degree $\deg^+(v)$ counts outgoing edges.

DfPath

A path is a sequence of vertices $v_0, v_1, \ldots, v_k$ where each consecutive pair $(v_{i-1}, v_i)$ is an edge. A simple path visits no vertex more than once.

DfCycle

A cycle is a path that starts and ends at the same vertex with no other repeated vertices. A graph with no cycles is called acyclic.

DfConnected Graph

A graph is connected if there is a path between every pair of vertices. A connected component is a maximal connected subgraph.

DfComplete Graph

A complete graph $K_n$ is a simple graph where every pair of distinct vertices is connected by an edge. It has exactly $\binom{n}{2} = \frac{n(n-1)}{2}$ edges.

DfBipartite Graph

A bipartite graph has vertices partitioned into two disjoint sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$ . No edge connects two vertices within the same set.

DfIsomorphism

Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there exists a bijection $f: V_1 \to V_2$ such that $\{u, v\} \in E_1$ if and only if $\{f(u), f(v)\} \in E_2$ .

Formulas

Handshaking Lemma

\sum_{v \in V} \deg(v) = 2|E|

Here,

$\deg(v)$ =Degree of vertex v
$|E|$ =Number of edges in the graph

Euler's Formula for Planar Graphs

|V| - |E| + |F| = 2

Here,

$|V|$ =Number of vertices
$|E|$ =Number of edges
$|F|$ =Number of faces (regions)

Max Edges in Simple Graph

|E| \leq \binom{|V|}{2} = \frac{|V|(|V|-1)}{2}

Here,

$|V|$ =Number of vertices

Max Edges in Bipartite Graph

|E| \leq |U| \cdot |V|

Here,

$|U|, |V|$ =Sizes of the two partitions

Python Implementations

Graph Representations

import numpy as np
from collections import defaultdict

# Adjacency Matrix
class AdjMatrixGraph:
    def __init__(self, n):
        self.n = n
        self.matrix = np.zeros((n, n), dtype=int)

    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        self.matrix[v][u] = weight  # undirected

    def has_edge(self, u, v):
        return self.matrix[u][v] != 0

    def degree(self, v):
        return int(self.matrix[v].sum())

# Adjacency List
class AdjListGraph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v, weight=1):
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))

    def neighbors(self, v):
        return self.graph[v]

    def degree(self, v):
        return len(self.graph[v])

# Example usage
g = AdjListGraph()
edges = [(0,1), (0,2), (1,2), (2,3), (3,4)]
for u, v in edges:
    g.add_edge(u, v)

print(f"Degree of node 2: {g.degree(2)}")
print(f"Neighbors of 2: {g.neighbors(2)}")

BFS and DFS Traversal

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)
        order = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return order

    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        order = [start]
        for neighbor in self.graph[start]:
            if neighbor not in visited:
                order.extend(self.dfs(neighbor, visited))
        return order

    def is_connected(self, n_vertices):
        visited = self.bfs(0)
        return len(visited) == n_vertices

g = Graph()
for u, v in [(0,1), (0,2), (1,3), (2,3), (3,4)]:
    g.add_edge(u, v)

print("BFS:", g.bfs(0))
print("DFS:", g.dfs(0))
print("Connected:", g.is_connected(5))

Euler Path Detection

def has_euler_path(graph, n_vertices):
    odd_degree = [v for v in range(n_vertices) if graph.degree(v) % 2 != 0]
    return len(odd_degree) == 0 or len(odd_degree) == 2

def euler_circuit_exists(graph, n_vertices):
    return all(graph.degree(v) % 2 == 0 for v in range(n_vertices))

Graph Coloring

DfGraph Coloring

A proper coloring assigns colors to vertices such that no two adjacent vertices share the same color. The chromatic number $\chi(G)$ is the minimum number of colors needed.

ThFour Color Theorem

Every planar graph can be properly colored with at most 4 colors.

def greedy_coloring(graph, n_vertices):
    result = [-1] * n_vertices
    result[0] = 0
    for u in range(1, n_vertices):
        available = set(range(n_vertices))
        for neighbor in graph[u]:
            if result[neighbor] != -1:
                available.discard(result[neighbor])
        result[u] = min(available)
    return result

def chromatic_number_upper_bound(n_vertices):
    return n_vertices  # Worst case: complete graph

Planarity

ThKuratowski's Theorem

A graph is planar if and only if it does not contain a subgraph homeomorphic to $K_5$ or $K_{3,3}$ .

ThPlanar Graph Edge Bound

For a simple planar graph with $|V| \geq 3$ : $|E| \leq 3|V| - 6$ .

Applications in AI/ML

ℹ️ Applications in AI and Machine Learning

Knowledge Graphs: Represent entities and relationships for reasoning and question answering
Graph Neural Networks (GNNs): Process graph-structured data for node classification and link prediction
Social Network Analysis: Identify communities, influencers, and information spread patterns
Combinatorial Optimization: Traveling salesman, vehicle routing, scheduling problems
Computer Vision: Scene graphs represent object relationships in images
Natural Language Processing: Dependency parsing creates trees; semantic networks capture meaning
Recommendation Systems: Bipartite user-item graphs for collaborative filtering

Common Mistakes

Mistake	Correction
Assuming all graphs are simple	A graph may have loops (edge from vertex to itself) and multiple edges between the same pair
Confusing directed and undirected degrees	In directed graphs, track in-degree and out-degree separately
Ignoring isolated vertices	Vertices with degree 0 still count toward $\\|V\\|$
Misapplying Euler's formula	Euler's formula only applies to connected planar graphs
Assuming planarity for dense graphs	$K_5$ has only 5 vertices but is non-planar
Forgetting the Handshaking Lemma implies even sum	The sum of all degrees is always even, so the number of odd-degree vertices is always even
Using BFS when DFS is needed	BFS finds shortest paths; DFS is better for cycle detection and topological sorting
Confusing isomorphism with same degree sequence	Same degree sequence does not guarantee isomorphism

Interview Questions

How would you detect a cycle in an undirected graph? Use DFS and check for back edges, or use Union-Find to detect if adding an edge connects two already-connected vertices.
What is the difference between BFS and DFS? BFS explores level by level using a queue, finding shortest paths in unweighted graphs. DFS explores as deep as possible using a stack/recursion, useful for topological sort and cycle detection.
How do you check if a graph is bipartite? Use BFS or DFS with 2-coloring. If we can color the graph with 2 colors such that no adjacent vertices share a color, it is bipartite.
What is the time complexity of graph traversal? BFS and DFS both run in $O(V + E)$ time using adjacency lists.
How do you find connected components? Run BFS/DFS from each unvisited vertex. Each traversal marks one connected component.
What is a topological sort and when is it used? A topological sort orders vertices in a DAG such that all edges go from earlier to later. Used in task scheduling and dependency resolution.
How do you find the shortest path in a weighted graph? Use Dijkstra's algorithm for non-negative weights, Bellman-Ford for graphs with negative weights, or Floyd-Warshall for all-pairs shortest paths.
What is graph coloring used for? Map coloring, register allocation in compilers, scheduling exams without conflicts, and frequency assignment in wireless networks.

Practice Problems

📝Practice: Handshaking Lemma

Problem: A graph has 6 vertices with degrees 2, 2, 3, 3, 4, 4. How many edges does it have?

💡Solution: Handshaking Lemma

$\sum \deg(v) = 2 + 2 + 3 + 3 + 4 + 4 = 18$ . By the Handshaking Lemma: $|E| = 18 / 2 = 9$ edges.

📝Practice: Euler Path

Problem: Does a graph with 4 vertices and edges {(0,1), (0,2), (0,3), (1,2)} have an Euler path?

💡Solution: Euler Path

Degrees: deg(0) = 3, deg(1) = 2, deg(2) = 2, deg(3) = 1. Two vertices have odd degree (0 and 3). By Euler's theorem, an Euler path exists starting at one odd-degree vertex and ending at the other.

📝Practice: Planarity

Problem: Can a connected graph with 8 vertices and 15 edges be planar?

💡Solution: Planarity

For planar graphs: $|E| \leq 3|V| - 6 = 3(8) - 6 = 18$ . Since $15 \leq 18$ , it could be planar. However, we must also verify no $K_5$ or $K_{3,3}$ subdivision exists.

📝Practice: Graph Coloring

Problem: What is the chromatic number of $K_4$ (complete graph on 4 vertices)?

💡Solution: Graph Coloring

Every vertex is adjacent to every other vertex, so each needs a unique color. $\chi(K_4) = 4$ .

Quick Reference

Concept	Formula/Description
Edges in $K_n$	$\frac{n(n-1)}{2}$
Handshaking Lemma	$\sum \deg(v) = 2\|E\|$
Euler's Formula	$\|V\| - \|E\| + \|F\| = 2$ (connected planar)
Planar edge bound	$\|E\| \leq 3\|V\| - 6$ for $\|V\| \geq 3$
Bipartite $K_{m,n}$ edges	$m \cdot n$
BFS time complexity	$O(V + E)$
DFS time complexity	$O(V + E)$
Chromatic number	Minimum colors for proper coloring
Euler path	Exists iff 0 or 2 odd-degree vertices
Hamilton cycle	NP-complete to determine existence

Cross-References

Trees → 075-discrete-trees.mdx: Trees are connected acyclic graphs; a special case of graph theory
Recurrence Relations → 076-discrete-recurrence.mdx: Graph traversal algorithms have recursive definitions
Number Theory → 077-discrete-number-theory.mdx: Modular arithmetic used in graph hashing
Boolean Algebra → 078-discrete-boolean.mdx: Boolean functions on graph properties
Automata Theory → 079-discrete-automata.mdx: State diagrams are directed graphs
Applications → 080-discrete-applications.mdx: Network flow, cryptography, and scheduling use graphs