Graph Theory: Structures and Connectivity

Graphs provide a formal framework for modeling relationships between discrete objects.

Fundamental Connectivity

Connected Graph: A path exists between every pair of vertices.
Components: The maximal connected subgraphs of a non-connected graph.
Bipartite Graphs: A graph whose vertices can be divided into two disjoint sets $U, V$ such that every edge connects a vertex in $U$ to one in $V$ .

Planar Graphs and Euler’s Formula

A graph is planar if it can be drawn in the plane without edges crossing.

Euler’s Formula: For any connected planar graph with $V$ vertices, $E$ edges, and $F$ faces: $V - E + F = 2$
Kuratowski’s Theorem: A graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_{5}$ (complete graph on 5 nodes) or $K_{3, 3}$ (complete bipartite graph).

Matchings and Flows

Matching: A set of edges without common vertices.
Hall’s Marriage Theorem: Provides a necessary and sufficient condition for a bipartite graph to have a perfect matching.
Network Flow: Modeling capacity on edges. The Max-Flow Min-Cut Theorem states that the maximum flow through a network is equal to the capacity of the minimum cut.

Graph Colorability

The Chromatic Number $χ (G)$ is the smallest number of colors needed to color the vertices of $G$ such that no two adjacent vertices share a color.

The Four Color Theorem: Any planar graph can be colored with no more than four colors.

Code: Finding Cycles (DFS)

def has_cycle(graph, node, visited, recursion_stack):
    visited.add(node)
    recursion_stack.add(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle(graph, neighbor, visited, recursion_stack):
                return True
        elif neighbor in recursion_stack:
            return True

    recursion_stack.remove(node)
    return False

Directed vs. Undirected

Undirected: Edges are like two-way streets.
Directed (Digraph): Edges have a direction (e.g., Twitter follows).

Trees

A tree is a connected graph with no cycles. In CS, trees are used for data structures (heaps, BSTs) and decision making.

Representation in Code: Adjacency List

type Graph = Map<number, number[]>;

const graph: Graph = new Map();
graph.set(1, [2, 3]);
graph.set(2, [1, 4]);
graph.set(3, [1]);
graph.set(4, [2]);

// Finding neighbors of node 1
console.log(graph.get(1)); // [2, 3]

Famous Problems

Shortest Path: Dijkstra’s Algorithm.
Traveling Salesperson: Finding the shortest cycle visiting all nodes.
Graph Coloring: Assigning colors such that no two adjacent nodes have the same color.

Exercise

Conceptual Check

Graph Theory