Fundamentals of Graph Theory

Overview

Graph theory is an important branch of discrete mathematics that studies graph structures composed of vertices and edges. It has broad applications in computer science, from network design to social network analysis, from circuit layout to scheduling problems.

1. Basic Concepts

1.1 Definition of a Graph

A graph \(G = (V, E)\) consists of a vertex set \(V\) and an edge set \(E\).

graph LR
    A((a)) --- B((b))
    A --- C((c))
    B --- C
    B --- D((d))
    C --- D

Types of graphs:

Type	Description	Edge Notation
Undirected graph	Edges have no direction	\(\{u, v\}\)
Directed graph	Edges have direction	\((u, v)\)
Weighted graph	Edges carry weights	\(w(u, v)\)
Simple graph	No self-loops or multiple edges	—
Multigraph	Multiple edges allowed	—
Complete graph	An edge between every pair of vertices	\(K_n\)

1.2 Basic Terminology

Degree: The degree \(\deg(v)\) of vertex \(v\) is the number of edges incident to it
In-degree / Out-degree: In a directed graph, \(\deg^+(v)\) and \(\deg^-(v)\)
Adjacency: If \(\{u, v\} \in E\), then \(u\) and \(v\) are adjacent
Path: A vertex sequence \(v_0, v_1, \ldots, v_k\) where consecutive vertices share an edge
Cycle: A path whose start and end vertices coincide
Connected: A path exists between any two vertices

1.3 Handshaking Lemma

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

Corollary: In any graph, the number of vertices with odd degree is even.

2. Special Graphs

2.1 Bipartite Graphs

The vertex set can be partitioned into two disjoint subsets \(V_1, V_2\) such that every edge connects a vertex in \(V_1\) to a vertex in \(V_2\).

graph LR
    subgraph V1
        a((a))
        b((b))
        c((c))
    end
    subgraph V2
        x((x))
        y((y))
    end
    a --- x
    a --- y
    b --- x
    c --- y

Characterization theorem: A graph \(G\) is bipartite \(\iff\) \(G\) contains no cycle of odd length.

Complete bipartite graph \(K_{m,n}\): Every vertex in \(V_1\) is connected to every vertex in \(V_2\).

2.2 Degree Sequences

The degree sequence of a graph is the non-decreasing sequence of all vertex degrees.

Erdos-Gallai theorem: A non-negative integer sequence \(d_1 \geq d_2 \geq \cdots \geq d_n\) is the degree sequence of some simple graph if and only if:

\(\sum d_i\) is even
For all \(k \in \{1, \ldots, n\}\): \(\sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{i=k+1}^{n} \min(d_i, k)\)

3. Eulerian and Hamiltonian Paths

3.1 Eulerian Paths and Circuits

Eulerian path: A path that traverses every edge exactly once
Eulerian circuit: An Eulerian path whose start and end vertices coincide

Euler's theorem:

Condition	Eulerian Circuit	Eulerian Path
Undirected connected graph	All vertices have even degree	Exactly 0 or 2 vertices of odd degree
Directed connected graph	In-degree = out-degree for all vertices	At most one vertex with out-degree - in-degree = 1, at most one with in-degree - out-degree = 1

The Konigsberg Bridge Problem

In 1736, Euler proved that it is impossible to traverse all seven bridges of Konigsberg without repeating any, because the graph has 4 vertices of odd degree. This is considered the origin of graph theory.

3.2 Hamiltonian Paths and Cycles

Hamiltonian path: A path that visits every vertex exactly once
Hamiltonian cycle: A Hamiltonian path whose start and end vertices coincide

Comparison with Eulerian paths:

Eulerian: Traverses every edge exactly once (polynomial-time decidable)
Hamiltonian: Visits every vertex exactly once (NP-complete)

Dirac's theorem: If a simple graph \(G\) has \(n \geq 3\) vertices and every vertex has degree \(\geq n/2\), then \(G\) has a Hamiltonian cycle.

Ore's theorem: If a simple graph \(G\) has \(n \geq 3\) vertices and for every pair of non-adjacent vertices \(u, v\), \(\deg(u) + \deg(v) \geq n\), then \(G\) has a Hamiltonian cycle.

4. Planar Graphs and Graph Coloring

4.1 Planar Graphs

Planar graph: A graph that can be drawn in the plane such that no edges cross.

Euler's formula: For a connected planar graph:

\[ V - E + F = 2 \]

where \(V\) is the number of vertices, \(E\) is the number of edges, and \(F\) is the number of faces (including the unbounded face).

Corollaries:

If \(V \geq 3\), then \(E \leq 3V - 6\)
If there are no triangles (minimum cycle length \(\geq 4\)), then \(E \leq 2V - 4\)

Kuratowski's theorem: A graph \(G\) is planar \(\iff\) \(G\) contains no subdivision of \(K_5\) or \(K_{3,3}\).

4.2 Graph Coloring

Vertex coloring: Assign a color to each vertex such that adjacent vertices receive different colors.

Chromatic number \(\chi(G)\): The minimum number of colors needed.

Graph	Chromatic Number
Even cycle \(C_{2n}\)	2
Odd cycle \(C_{2n+1}\)	3
Complete graph \(K_n\)	\(n\)
Bipartite graph	2
Tree	2
Planar graph	\(\leq 4\)

Four Color Theorem (1976, computer-assisted proof): The chromatic number of any planar graph is \(\leq 4\).

Greedy coloring algorithm:

def greedy_coloring(graph, vertices):
    """Greedy graph coloring"""
    color = {}
    for v in vertices:
        # Collect colors used by neighbors
        used = {color[u] for u in graph[v] if u in color}
        # Assign the smallest available color
        c = 0
        while c in used:
            c += 1
        color[v] = c
    return color

Limitations of Greedy Coloring

The result of greedy coloring depends on vertex ordering. In the worst case, it may use \(\Delta(G) + 1\) colors (\(\Delta\) being the maximum degree), and does not necessarily achieve \(\chi(G)\).

5. Trees

5.1 Definition and Properties

Tree: A connected acyclic graph.

Equivalent definitions (for a graph with \(n\) vertices):

Connected with \(n - 1\) edges
Acyclic with \(n - 1\) edges
Exactly one path between any two vertices
Connected, and removing any edge disconnects the graph
Acyclic, and adding any edge creates exactly one cycle

5.2 Spanning Trees

Spanning tree: A tree that contains all vertices of the graph.

Cayley's formula: \(K_n\) has \(n^{n-2}\) distinct spanning trees.

\(n\)	Number of spanning trees \(n^{n-2}\)
2	1
3	3
4	16
5	125

6. Network Flow

6.1 Maximum Flow Problem

Given a directed graph \(G = (V, E)\), a source \(s\), a sink \(t\), and a capacity \(c(u,v)\) for each edge \((u,v)\), find the maximum flow from \(s\) to \(t\).

Flow constraints:

Capacity constraint: \(0 \leq f(u, v) \leq c(u, v)\)
Flow conservation: For \(v \neq s, t\), \(\sum_u f(u, v) = \sum_w f(v, w)\)

6.2 Max-Flow Min-Cut Theorem

\[ \max \text{flow} = \min \text{cut} \]

Cut: A partition of \(V\) into \(S\) and \(T = V \setminus S\) (\(s \in S, t \in T\)); the capacity of the cut is:

\[ c(S, T) = \sum_{u \in S, v \in T} c(u, v) \]

6.3 Ford-Fulkerson Method

while there exists an augmenting path P from s to t:
    compute the bottleneck capacity Δ along P
    augment flow by Δ along P
    update the residual graph

Time complexity: \(O(|E| \cdot |f^*|)\), where \(f^*\) is the maximum flow value.

Edmonds-Karp algorithm: Uses BFS to find the shortest augmenting path, with complexity \(O(VE^2)\).

7. Introduction to Ramsey Theory

7.1 Basic Idea

Ramsey theory studies the principle that "complete disorder is impossible" -- any sufficiently large structure necessarily contains certain ordered substructures.

7.2 Ramsey Numbers

\(R(s, t)\) is the smallest positive integer \(n\) such that any 2-coloring (red/blue) of the edges of \(K_n\) must contain either a red \(K_s\) or a blue \(K_t\).

Known values:

\(R(s,t)\)	\(t=3\)	\(t=4\)	\(t=5\)
\(s=3\)	6	9	14
\(s=4\)	9	18	25
\(s=5\)	14	25	43--48

Difficulty of Computing Ramsey Numbers

The exact value of \(R(5,5)\) remains unknown; we only know \(43 \leq R(5,5) \leq 48\). Erdos once said: "If aliens threatened to destroy Earth unless we computed \(R(5,5)\), we should marshal all our computers to the task. But if they demanded \(R(6,6)\), we should try to destroy the aliens."

Upper bound: \(R(s, t) \leq \binom{s+t-2}{s-1}\)

8. Graph Representation and Storage

8.1 Adjacency Matrix

An \(n \times n\) matrix \(A\) where \(A[i][j] = 1\) indicates that edge \((i, j)\) exists.

Space: \(O(n^2)\)
Edge query: \(O(1)\)
Neighbor traversal: \(O(n)\)

8.2 Adjacency List

Each vertex maintains a list of its neighbors.

Space: \(O(n + m)\)
Edge query: \(O(\deg(v))\)
Neighbor traversal: \(O(\deg(v))\)

Recommendation: Use adjacency matrices for dense graphs; use adjacency lists for sparse graphs (\(m \ll n^2\)).

References

Diestel, Graph Theory (graduate-level classic textbook)
West, Introduction to Graph Theory
Bondy & Murty, Graph Theory

Related sections: