Graph Theory

Last updated: December 2024

Disclaimer: These are my personal notes compiled for my own reference and learning. They may contain errors, incomplete information, or personal interpretations. While I strive for accuracy, these notes are not peer-reviewed and should not be considered authoritative sources. Please consult official textbooks, research papers, or other reliable sources for academic or professional purposes.

1. Basic Definitions

A graph $G = (V, E)$ consists of a set of vertices $V$ and a set of edges $E$, where each edge connects two vertices.

1.1 Types of Graphs

Simple Graph: No self-loops or multiple edges
Multigraph: Multiple edges allowed between vertices
Directed Graph (Digraph): Edges have direction
Weighted Graph: Edges have associated weights
Complete Graph: Every pair of vertices is connected
Bipartite Graph: Vertices can be divided into two disjoint sets

1.2 Basic Parameters

Order: Number of vertices $|V| = n$
Size: Number of edges $|E| = m$
Degree: $\deg(v)$ = number of edges incident to vertex $v$
Maximum Degree: $\Delta(G) = \max_{v \in V} \deg(v)$
Minimum Degree: $\delta(G) = \min_{v \in V} \deg(v)$

2. Fundamental Theorems

2.1 Handshaking Lemma

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

Corollary: The number of vertices with odd degree is even.

2.2 Bounds on Edges

For a simple graph with $n$ vertices:

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

3. Graph Connectivity

3.1 Connectivity Definitions

Connected: Path exists between every pair of vertices
Component: Maximal connected subgraph
Cut Vertex: Vertex whose removal increases components
Bridge: Edge whose removal increases components
$k$-connected: Remains connected after removing any $k-1$ vertices

3.2 Connectivity Numbers

Vertex Connectivity: $\kappa(G)$ = minimum vertices to disconnect
Edge Connectivity: $\lambda(G)$ = minimum edges to disconnect
Whitney's Inequality: $\kappa(G) \leq \lambda(G) \leq \delta(G)$

4. Trees and Forests

4.1 Tree Properties

A tree is a connected acyclic graph. Equivalent characterizations:

Connected with $n-1$ edges
Acyclic with $n-1$ edges
Unique path between every pair of vertices
Minimal connected graph
Maximal acyclic graph

4.2 Spanning Trees

A spanning tree of $G$ is a subgraph that is a tree and includes all vertices.

Cayley's Formula: The number of labeled spanning trees of $K_n$ is $n^{n-2}$.

4.3 Minimum Spanning Tree Algorithms

Kruskal's Algorithm

Sort edges by weight
Add edges if they don't create a cycle
Use Union-Find for cycle detection

Time complexity: $O(m \log m)$

Prim's Algorithm

Start with arbitrary vertex
Repeatedly add minimum weight edge to tree
Use priority queue for efficiency

Time complexity: $O(m \log n)$ with binary heap

5. Shortest Path Algorithms

5.1 Single-Source Shortest Paths

Dijkstra's Algorithm

For non-negative weights:

d[v] = \min(d[v], d[u] + w(u,v))

Time complexity: $O((n + m) \log n)$ with Fibonacci heap

Bellman-Ford Algorithm

Handles negative weights, detects negative cycles:

Time complexity: $O(nm)$

5.2 All-Pairs Shortest Paths

Floyd-Warshall Algorithm

d[i][j] = \min(d[i][j], d[i][k] + d[k][j])

Time complexity: $O(n^3)$

6. Graph Coloring

6.1 Vertex Coloring

A proper coloring assigns colors to vertices such that adjacent vertices have different colors.

Chromatic Number: $\chi(G)$ = minimum colors needed
Clique Number: $\omega(G)$ = size of largest clique
Independence Number: $\alpha(G)$ = size of largest independent set

6.2 Important Results

$\chi(G) \geq \omega(G)$
$\chi(G) \leq \Delta(G) + 1$ (Greedy bound)
$\chi(G) \leq \Delta(G)$ if $G$ is not complete or odd cycle (Brooks' theorem)
$\alpha(G) \cdot \chi(G) \geq n$

6.3 Four Color Theorem

Every planar graph is 4-colorable. This was the first major theorem proved using computer assistance.

7. Planar Graphs

7.1 Euler's Formula

For a connected planar graph:

$$n - m + f = 2$$

where $f$ is the number of faces (including the outer face).

7.2 Consequences of Euler's Formula

For $n \geq 3$: $m \leq 3n - 6$
For triangle-free graphs with $n \geq 3$: $m \leq 2n - 4$
Every planar graph has a vertex of degree $\leq 5$

7.3 Kuratowski's Theorem

A graph is planar if and only if it contains no subdivision of $K_5$ or $K_{3,3}$.

8. Matching Theory

8.1 Basic Definitions

Matching: Set of edges with no common vertices
Maximum Matching: Matching with maximum number of edges
Perfect Matching: Matching covering all vertices
Vertex Cover: Set of vertices covering all edges

8.2 König's Theorem

In a bipartite graph:

\text{size of maximum matching} = \text{size of minimum vertex cover}

8.3 Hall's Marriage Theorem

A bipartite graph $G = (A \cup B, E)$ has a matching saturating $A$ if and only if:

|N(S)| \geq |S| \text{ for all } S \subseteq A

where $N(S)$ is the neighborhood of $S$.

9. Network Flows

9.1 Maximum Flow Problem

Given a flow network with source $s$ and sink $t$, find maximum flow from $s$ to $t$.

9.2 Max-Flow Min-Cut Theorem

The maximum flow equals the minimum cut capacity.

9.3 Ford-Fulkerson Algorithm

Find augmenting path from source to sink
Augment flow along this path
Repeat until no augmenting path exists

10. Eulerian and Hamiltonian Graphs

10.1 Eulerian Paths and Cycles

Eulerian Path: Path using every edge exactly once
Eulerian Cycle: Cycle using every edge exactly once

Theorem: A connected graph has an Eulerian cycle if and only if every vertex has even degree.

10.2 Hamiltonian Paths and Cycles

Hamiltonian Path: Path visiting every vertex exactly once
Hamiltonian Cycle: Cycle visiting every vertex exactly once

Dirac's Theorem: If $\delta(G) \geq n/2$ in a graph with $n \geq 3$, then $G$ is Hamiltonian.

11. Graph Algorithms Implementation

# Python implementation of key graph algorithms
from collections import defaultdict, deque
import heapq

class Graph:
    def __init__(self, directed=False):
        self.directed = directed
        self.adj_list = defaultdict(list)
        self.vertices = set()
    
    def add_edge(self, u, v, weight=1):
        self.adj_list[u].append((v, weight))
        self.vertices.update([u, v])
        if not self.directed:
            self.adj_list[v].append((u, weight))
    
    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        
        visited.add(start)
        result = [start]
        
        for neighbor, _ in self.adj_list[start]:
            if neighbor not in visited:
                result.extend(self.dfs(neighbor, visited))
        
        return result
    
    def bfs(self, start):
        visited = set([start])
        queue = deque([start])
        result = []
        
        while queue:
            vertex = queue.popleft()
            result.append(vertex)
            
            for neighbor, _ in self.adj_list[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return result
    
    def dijkstra(self, start):
        distances = {v: float('inf') for v in self.vertices}
        distances[start] = 0
        previous = {}
        pq = [(0, start)]
        
        while pq:
            current_dist, current = heapq.heappop(pq)
            
            if current_dist > distances[current]:
                continue
            
            for neighbor, weight in self.adj_list[current]:
                distance = current_dist + weight
                
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous[neighbor] = current
                    heapq.heappush(pq, (distance, neighbor))
        
        return distances, previous
    
    def kruskal_mst(self):
        # Union-Find for cycle detection
        parent = {}
        rank = {}
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True
        
        # Initialize Union-Find
        for v in self.vertices:
            parent[v] = v
            rank[v] = 0
        
        # Get all edges and sort by weight
        edges = []
        for u in self.adj_list:
            for v, weight in self.adj_list[u]:
                if not self.directed and u <= v:  # Avoid duplicates
                    edges.append((weight, u, v))
                elif self.directed:
                    edges.append((weight, u, v))
        
        edges.sort()
        mst_edges = []
        total_weight = 0
        
        for weight, u, v in edges:
            if union(u, v):
                mst_edges.append((u, v, weight))
                total_weight += weight
        
        return mst_edges, total_weight
    
    def is_bipartite(self):
        color = {}
        
        for start in self.vertices:
            if start in color:
                continue
            
            queue = deque([start])
            color[start] = 0
            
            while queue:
                u = queue.popleft()
                for v, _ in self.adj_list[u]:
                    if v not in color:
                        color[v] = 1 - color[u]
                        queue.append(v)
                    elif color[v] == color[u]:
                        return False
        
        return True
    
    def topological_sort(self):
        if not self.directed:
            raise ValueError("Topological sort only applies to directed graphs")
        
        in_degree = {v: 0 for v in self.vertices}
        for u in self.adj_list:
            for v, _ in self.adj_list[u]:
                in_degree[v] += 1
        
        queue = deque([v for v in self.vertices if in_degree[v] == 0])
        result = []
        
        while queue:
            u = queue.popleft()
            result.append(u)
            
            for v, _ in self.adj_list[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    queue.append(v)
        
        if len(result) != len(self.vertices):
            raise ValueError("Graph contains a cycle")
        
        return result
    
    def floyd_warshall(self):
        vertices = list(self.vertices)
        n = len(vertices)
        vertex_to_index = {v: i for i, v in enumerate(vertices)}
        
        # Initialize distance matrix
        dist = [[float('inf')] * n for _ in range(n)]
        
        # Distance from vertex to itself is 0
        for i in range(n):
            dist[i][i] = 0
        
        # Fill in edge weights
        for u in self.adj_list:
            for v, weight in self.adj_list[u]:
                i, j = vertex_to_index[u], vertex_to_index[v]
                dist[i][j] = weight
        
        # Floyd-Warshall algorithm
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        
        return dist, vertices

def graph_coloring_greedy(graph):
    """Greedy graph coloring algorithm"""
    colors = {}
    vertices = list(graph.vertices)
    
    for vertex in vertices:
        # Find colors used by neighbors
        used_colors = set()
        for neighbor, _ in graph.adj_list[vertex]:
            if neighbor in colors:
                used_colors.add(colors[neighbor])
        
        # Assign smallest available color
        color = 0
        while color in used_colors:
            color += 1
        colors[vertex] = color
    
    return colors

def detect_cycle(graph):
    """Detect cycle in undirected graph using DFS"""
    visited = set()
    
    def dfs(vertex, parent):
        visited.add(vertex)
        
        for neighbor, _ in graph.adj_list[vertex]:
            if neighbor not in visited:
                if dfs(neighbor, vertex):
                    return True
            elif parent != neighbor:
                return True
        
        return False
    
    for vertex in graph.vertices:
        if vertex not in visited:
            if dfs(vertex, None):
                return True
    
    return False

# Example usage
if __name__ == "__main__":
    # Create a sample graph
    g = Graph()
    g.add_edge('A', 'B', 4)
    g.add_edge('A', 'C', 2)
    g.add_edge('B', 'C', 1)
    g.add_edge('B', 'D', 5)
    g.add_edge('C', 'D', 8)
    g.add_edge('C', 'E', 10)
    g.add_edge('D', 'E', 2)
    
    print("DFS from A:", g.dfs('A'))
    print("BFS from A:", g.bfs('A'))
    
    distances, _ = g.dijkstra('A')
    print("Shortest distances from A:", distances)
    
    mst_edges, total_weight = g.kruskal_mst()
    print("MST edges:", mst_edges)
    print("MST total weight:", total_weight)
    
    print("Is bipartite:", g.is_bipartite())
    print("Has cycle:", detect_cycle(g))
    
    colors = graph_coloring_greedy(g)
    print("Graph coloring:", colors)

12. Applications

12.1 Computer Networks

Routing algorithms
Network reliability
Bandwidth optimization

12.2 Social Networks

Community detection
Influence maximization
Recommendation systems

12.3 Transportation

Route planning
Traffic flow optimization
Public transit networks

13. References

West, D. B. (2001). Introduction to Graph Theory.
Diestel, R. (2017). Graph Theory.
Cormen, T. H., et al. (2009). Introduction to Algorithms.