Graph Theory

An adjacency matrix represents a graph as an n×n matrix A, where n is the number of vertices, and entry A[i][j] indicates whether an edge exists between vertex i and vertex j. For an undirected graph, the matrix is symmetric (A[i][j] = A[j][i]); for a weighted graph, entries hold edge weights instead of just 0/1. This representation trades space (O(n²), even for sparse graphs) for speed of edge lookups (O(1)) and lets graph questions be answered with linear-algebra tools — for instance, the number of walks of length k between two vertices is given by the (i,j) entry of A^k.

A bipartite graph is a graph whose vertices can be split into two disjoint sets, X and Y, such that every edge connects a vertex in X to a vertex in Y — no edge ever joins two vertices within the same set. Bipartite graphs naturally model matching problems between two distinct kinds of objects: job applicants and job openings, students and schools, or buyers and sellers. A fundamental theorem states that a graph is bipartite if and only if it contains no odd-length cycle, giving an easy algorithmic test via a two-coloring attempt during BFS or DFS.

A directed graph (or digraph) is a graph in which edges have a direction, running from one vertex to another rather than simply connecting them. Each edge is an ordered pair (u, v), meaning there is a connection from u to v but not necessarily from v to u. Directed graphs naturally model asymmetric relationships — following on social media, one-way streets, task dependencies, and web hyperlinks. Key notions unique to digraphs include in-degree and out-degree, directed paths, strongly connected components, and directed acyclic graphs (DAGs), which forbid directed cycles and underlie scheduling and dependency resolution.

An Eulerian path traverses every EDGE of a graph exactly once; a Hamiltonian path visits every VERTEX exactly once. Despite the similar-sounding names, they behave completely differently: Euler's 1736 solution to the Seven Bridges of Königsberg gave a clean criterion — a connected graph has an Eulerian circuit if and only if every vertex has even degree, and an Eulerian path (not necessarily closed) if and only if exactly zero or two vertices have odd degree. No comparably simple criterion is known for Hamiltonian paths; determining whether one exists is NP-complete in general, making it one of the hardest classical problems in graph theory.

A graph is connected if there is a path between every pair of vertices; otherwise it splits into two or more connected components, each a maximal set of mutually reachable vertices. Connectivity can be measured more finely: vertex connectivity κ(G) is the minimum number of vertices whose removal disconnects the graph (or reduces it to a single vertex), and edge connectivity λ(G) is the analogous minimum number of edges. A single vertex whose removal disconnects the graph is called a cut vertex (or articulation point), and a single edge with the same effect is a bridge. These measures quantify network robustness — how many failures a network can tolerate before it fragments.

Two graphs are isomorphic if there exists a bijection between their vertex sets that preserves adjacency: an edge exists between two vertices in one graph exactly when an edge exists between their corresponding vertices in the other. Isomorphic graphs are structurally identical — they may look different when drawn (different vertex labels, positions) but represent the same abstract structure. Checking two graphs are NOT isomorphic is often easy using invariants (properties preserved by isomorphism, like degree sequence, number of vertices/edges, or number of triangles) that must match if the graphs are isomorphic; but proving two graphs ARE isomorphic, or finding an efficient general algorithm, remains a famously open problem — graph isomorphism is one of the few problems believed to be neither NP-complete nor solvable in polynomial time.

A planar graph is a graph that can be drawn on a plane with no two edges crossing. Euler's formula relates the number of vertices, edges, and faces of any connected planar drawing: V - E + F = 2. This formula yields a hard edge bound for simple planar graphs: E ≤ 3V - 6 (for V ≥ 3), which is used to prove that graphs like K5 (the complete graph on 5 vertices) and K3,3 (the complete bipartite graph on two sets of 3) are NOT planar. Kuratowski's theorem sharpens this into a full characterization: a graph is planar if and only if it contains no subdivision of K5 or K3,3 as a subgraph. Planarity matters directly for circuit board layout, where crossing wires require extra layers.

A spanning tree of a connected graph G is a subgraph that includes every vertex of G, is itself a tree (connected, no cycles), and uses only edges already present in G. Removing any cycle-forming edge from a connected graph while keeping it connected eventually leaves a spanning tree — the minimal 'skeleton' that still touches every vertex. Most connected graphs admit many different spanning trees, and counting them exactly is a classical question: Cayley's formula gives a strikingly simple count (n^(n-2)) for the complete graph, while Kirchhoff's matrix-tree theorem gives a general recipe (a single determinant) for any connected graph. Spanning trees underlie network design (minimum-cost backbone wiring), broadcast/routing protocols, and are the discrete-math ancestor of the minimum spanning tree algorithms (Kruskal's, Prim's) used throughout computer science.

A clique in a graph is a set of vertices that are all pairwise adjacent — a fully-connected 'mini complete graph' sitting inside the larger one. An independent set is the opposite extreme: a set of vertices with no edges between any of them at all. The two notions are mirror images of each other through graph complementation: a clique in G is exactly an independent set in G's complement Ḡ (the graph with the same vertices but edges swapped for non-edges), so every clique-finding fact has an independent-set twin. Both are central to combinatorics: finding the largest clique (clique number ω(G)) or largest independent set (independence number α(G)) are both NP-hard in general, and Ramsey theory asks a deeper question — how large must a graph be before it's forced to contain a clique or independent set of a given size, no matter how its edges are arranged.

Euler's formula states that for any connected graph drawn in the plane without edge crossings, the vertices, edges, and faces (regions the drawing divides the plane into, including the single unbounded outer face) always satisfy V − E + F = 2. Euler stated the polyhedral version of this in a 1750 letter to Goldbach (giving V − E + F = 2 for the vertices, edges, and faces of any convex polyhedron), and the same identity applies unchanged to any connected planar graph drawing, since a convex polyhedron's surface can always be flattened into a planar graph. The formula is the single most useful counting tool for planar graphs: it forces the edge bounds that prove K5 and K3,3 are non-planar, it constrains how many faces a map or circuit layout can have, and its invariance under different planar drawings of the SAME graph shows that V − E + F is a genuine topological property, not an artifact of how you happen to draw it.

Graph coloring assigns labels ('colors') to the vertices of a graph so that no two adjacent vertices share the same color. The chromatic number χ(G) is the minimum number of colors needed. Coloring problems are notoriously hard in general (determining χ(G) is NP-hard), but the concept models an enormous range of scheduling and assignment problems, from exam timetabling to register allocation in compilers to the famous Four Color Theorem, which states that any planar map can be colored with just four colors so no two adjacent regions share a color.

A matching in a graph is a set of edges with no two sharing a vertex — every vertex touches at most one matching edge. A maximum matching has the largest possible number of edges, and a perfect matching covers every vertex. For bipartite graphs, Hall's marriage theorem gives a clean existence criterion for a perfect matching: one exists (saturating one side) if and only if every subset S of that side has at least |S| neighbors on the other side (the 'marriage condition'). The Hungarian algorithm finds a maximum matching (or minimum-cost perfect matching) in bipartite graphs in polynomial time, and matching problems reduce directly to network flow problems, connecting the two areas.

A spanning tree of a connected graph is a subgraph that includes every vertex and is itself a tree — connected and cycle-free, using exactly n-1 edges for n vertices. A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible, among all spanning trees of a weighted graph. Two classical greedy algorithms compute an MST efficiently: Kruskal's algorithm sorts all edges by weight and adds each one that doesn't create a cycle, while Prim's algorithm grows a single tree outward by always adding the cheapest edge connecting the tree to a new vertex. Both are correct because of the 'cut property': the cheapest edge crossing any cut of the graph is always safe to include in some MST.

A flow network is a directed graph where each edge has a capacity, and the goal is to push as much 'flow' as possible from a source vertex s to a sink vertex t without exceeding any edge's capacity, while conserving flow at every other vertex (what flows in must flow out). The maximum flow problem asks for the largest such flow value. The Ford–Fulkerson method finds it by repeatedly locating an 'augmenting path' — a path from s to t along which more flow can still be pushed — and increasing flow along it until no augmenting path remains. The max-flow min-cut theorem guarantees that this maximum flow value exactly equals the minimum total capacity of any 's-t cut' (a partition separating s from t), tying the problem to network vulnerability analysis.

A topological sort of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every directed edge (u, v), u appears before v in the ordering. Such an ordering exists if and only if the graph has no directed cycle — this is precisely why the graph must be a DAG. Topological sort is typically computed either via a DFS-based algorithm that appends vertices to the front of the order as they finish, or via Kahn's algorithm, which repeatedly removes vertices with in-degree 0. Topological sorts are generally not unique; a DAG can admit multiple valid orderings whenever some vertices are unconstrained relative to each other.

Graph traversal is the process of systematically visiting every vertex in a graph. The two fundamental strategies are breadth-first search (BFS), which explores all neighbors of a vertex before moving further out, and depth-first search (DFS), which plunges as deep as possible along one branch before backtracking. Tree traversal is a special case of graph traversal. These algorithms are the foundation on which shortest-path, connectivity, and cycle-detection algorithms are built.

The shortest path problem asks for a path between two vertices in a graph such that the sum of the weights of its edges is minimized. When all edges have equal weight, BFS solves it directly; when edges carry different (non-negative) weights, Dijkstra's algorithm is the standard solution.

A graph is a mathematical structure made of vertices (nodes) connected by edges. Graphs model networks of every kind — social connections, road maps, computer networks, dependency chains — anywhere relationships between discrete objects matter more than the objects' individual properties.

The degree sequence of a graph is the list of all vertex degrees, usually sorted in non-increasing order. It's a simple invariant — just count edges at each vertex — but it packs a surprising amount of structural information: it instantly tells you the number of edges (via the handshaking lemma), and a purely arithmetic test (the Erdős–Gallai theorem) tells you whether ANY simple graph could ever produce a given sequence, without having to construct one. Not every list of non-negative integers is a valid degree sequence — a sequence that passes the test is called 'graphical'. Degree sequences show up whenever a network's connectivity pattern matters more than its exact wiring: internet router degree distributions, social network 'friend counts', and chemistry (atom valences in molecular graphs) are all degree-sequence questions in disguise.

A tree is an undirected graph in which every pair of distinct vertices is connected by exactly one path — equivalently, a connected, acyclic graph. A forest is a disjoint union of trees (an acyclic graph that need not be connected). Trees are the simplest nontrivial graphs and underlie hierarchical structures everywhere: file systems, organization charts, family genealogies, decision trees, and the parse trees compilers build from source code.

The chromatic polynomial P(G, k) counts the number of ways to properly color the vertices of a graph G using at most k colors, where 'proper' means no two adjacent vertices share a color. Introduced by George Birkhoff in 1912 as a tool to attack the Four Color Theorem, it turns graph coloring — normally a yes/no existence question ('can this map be colored with 4 colors?') — into a counting question whose answer is always an honest polynomial in k. Plugging in k = 4 and checking whether P(G, 4) > 0 tells you whether G is 4-colorable; the polynomial's degree, leading coefficient, and sign pattern also encode structural facts like the number of vertices and edges of G.