Graph Theory Fundamentals

Introduction

Graph theory is the mathematical study of relationships between objects. A graph consists of vertices (also called nodes) connected by edges. This simple structure can model an enormous variety of real-world situations: social networks, transportation systems, molecular structures, computer networks, scheduling problems, and countless others.

The field originated in 1736 when Leonhard Euler solved the famous Seven Bridges of Königsberg problem by proving that no walk could cross each of the seven bridges exactly once. This work laid the foundation for both graph theory and topology.

Graph theory has become essential in computer science for data structures and algorithms, in operations research for optimization, in chemistry for molecular modeling, and in social sciences for network analysis. We will develop the fundamental definitions, properties, and theorems that form the basis of this rich field.

Basic Definitions

Graphs

A graph G=(V,E) consists of a finite set V of vertices and a set E of edges. Each edge connects two vertices. The number of vertices is denoted n=|V| and the number of edges is denoted m=|E|

In an undirected graph, each edge is an unordered pair {u,v} of distinct vertices. In a directed graph (or digraph), edges are ordered pairs (u,v) representing an edge from u to v

A simple graph has no loops (edges from a vertex to itself) and no multiple edges between the same pair of vertices. Unless otherwise specified, we consider simple undirected graphs.

Adjacency and Incidence

Two vertices u and v are adjacent (or neighbors) if there is an edge between them. An edge e is incident to a vertex v if v is an endpoint of e

The neighborhood of a vertex v denoted N(v) is the set of all vertices adjacent to v. The closed neighborhood N[v]=N(v)∪{v} includes v itself.

Degree

The degree of a vertex v denoted deg*(v) or d(v) is the number of edges incident to v. Equivalently, deg*(v)=|N(v)|

A vertex of degree zero is called isolated. A vertex of degree one is called a leaf or pendant vertex. The minimum degree in a graph is denoted δ(G) and the maximum degree is denoted Δ(G).

A graph is called kregular if every vertex has degree k A 3-regular graph is also called cubic.

The Handshaking Lemma

One of the most fundamental results in graph theory states:

(∑_v∈V^)(deg)*(v)=2*|E|

Each edge contributes exactly 2 to the total degree (once for each endpoint). An immediate corollary is that the number of vertices of odd degree must be even.

Paths and Connectivity

Walks, Paths, and Cycles

A walk in a graph is a sequence of vertices (v_0),(v_1),…,(v_k) such that (v_i−1) and (v_i) are adjacent for each i. The length of the walk is k (the number of edges).

A path is a walk with no repeated vertices. A cycle is a walk with (v_0)=(v_k) and no other repeated vertices.

The path graph (P_n) has n vertices connected in a line. The cycle graph (C_n) has n vertices connected in a closed loop.

Connectivity

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

The distance d(u,v) between vertices u and v is the length of the shortest path from u to v (or ∞ if no path exists). The diameter of a graph is the maximum distance between any two vertices.

Special Types of Graphs

Complete Graphs

The complete graph (K_n) has n vertices with an edge between every pair of distinct vertices. It has ([n],[2])=(n*(n-1))/2 edges, and every vertex has degree n−1

Bipartite Graphs

A graph is bipartite if its vertices can be partitioned into two disjoint sets A and B such that every edge connects a vertex in A to a vertex in B Equivalently, a graph is bipartite if and only if it contains no odd cycles.

The complete bipartite graph (K_m,n) has parts of sizes m and n with every possible edge between the parts. It has m*n edges.

Trees

A tree is a connected graph with no cycles. Equivalently, a tree on n vertices has exactly n−1 edges, and there is a unique path between any two vertices.

A forest is a graph with no cycles (a disjoint union of trees). A rooted tree has a designated root vertex, defining parent-child relationships.

Trees are fundamental in computer science for data structures (binary search trees, heaps) and algorithms (spanning trees, decision trees).

Graph Representations

Adjacency Matrix

The adjacency matrix A of a graph with n vertices is an n×n matrix where (A_i*j)=1 if vertices i and j are adjacent, and (A_i*j)=0 otherwise.

For undirected graphs, A is symmetric. The entry (Ak)(i*j) counts the number of walks of length k from i to j.

Adjacency List

An adjacency list stores, for each vertex, a list of its neighbors. This representation uses O*(n+m) space, compared to O(n2) for the adjacency matrix, making it more efficient for sparse graphs.

Eulerian and Hamiltonian Paths

Eulerian Paths and Circuits

An Eulerian path is a walk that uses every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.

A connected graph has an Eulerian circuit if and only if every vertex has even degree. It has an Eulerian path (but not circuit) if and only if exactly two vertices have odd degree (these must be the endpoints).

This was Euler's original theorem from the Königsberg bridge problem. The condition can be checked in linear time, and an Eulerian path can be found efficiently using Hierholzer's algorithm.

Hamiltonian Paths and Cycles

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that returns to the starting vertex.

Unlike Eulerian paths, there is no simple characterization of graphs with Hamiltonian paths. Determining whether a Hamiltonian path exists is NP-complete. However, sufficient conditions exist:

Dirac's Theorem: If G has n≥3 vertices and every vertex has degree at least n/2 then G has a Hamiltonian cycle.

Graph Coloring

A proper vertex coloring assigns colors to vertices such that no two adjacent vertices have the same color. The chromatic number χ(G) is the minimum number of colors needed.

A graph is kcolorable if χ(G)≤k Bipartite graphs are exactly the 2-colorable graphs.

The Four Color Theorem states that every planar graph is 4-colorable. This means any map can be colored with four colors such that no two adjacent regions have the same color.

Summary

A graph G=(V,E) consists of vertices and edges connecting them. The degree of a vertex is the number of incident edges, and the Handshaking Lemma states that (∑_^)(deg)*(v)=2*|E|

A path visits vertices without repetition; a cycle returns to its start. A graph is connected if every pair of vertices has a path between them. Trees are connected acyclic graphs with n−1 edges.

Special graph families include complete graphs (K_n) bipartite graphs, and cycles (C_n). Graphs can be represented by adjacency matrices or adjacency lists.

Eulerian paths (using every edge once) have a complete characterization via vertex degrees. Hamiltonian paths (visiting every vertex once) are harder to characterize computationally. Graph coloring assigns colors to vertices to avoid adjacent vertices sharing colors.