Graph Theory Basics - Core Definitions

Graph theory provides a mathematical framework for studying pairwise relationships between objects. Graphs model networks, connections, and structures across computer science, operations research, social sciences, and pure mathematics.

DefinitionGraph

A graph $G = (V, E)$ consists of:

A set $V$ of vertices (or nodes)
A set $E$ of edges, where each edge connects two vertices

An edge between vertices $u$ and $v$ is denoted $\{u, v\}$ or simply $uv$ . If edge $e = uv$ exists, we say $u$ and $v$ are adjacent or neighbors, and $e$ is incident to both $u$ and $v$ .

Graphs can be undirected (edges have no direction) or directed (each edge has a source and target vertex, forming a digraph). Unless stated otherwise, we consider simple undirected graphs: no multiple edges between vertices and no loops (edges from a vertex to itself).

DefinitionDegree

The degree of a vertex $v$ , denoted $\deg(v)$ or $d(v)$ , is the number of edges incident to $v$ . In a directed graph, we distinguish in-degree $\deg^-(v)$ (incoming edges) and out-degree $\deg^+(v)$ (outgoing edges).

A vertex with degree 0 is isolated. A vertex with degree 1 is a leaf (or pendant vertex).

ExampleHandshaking Lemma

In any graph $G = (V, E)$ , the sum of all vertex degrees equals twice the number of edges: $\sum_{v \in V} \deg(v) = 2|E|$

This follows because each edge contributes 1 to the degree of each of its two endpoints. A corollary: every graph has an even number of odd-degree vertices (since the sum must be even).

DefinitionPaths and Cycles

A path in a graph is a sequence of vertices $v_0, v_1, \ldots, v_k$ where each consecutive pair is connected by an edge. The length of the path is $k$ (the number of edges).

A path is simple if no vertex is repeated. A cycle is a path $v_0, v_1, \ldots, v_k$ where $v_0 = v_k$ and all other vertices are distinct. The girth of a graph is the length of its shortest cycle (or $\infty$ if acyclic).

DefinitionConnectivity

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

The distance $d(u,v)$ between vertices $u$ and $v$ is the length of the shortest path between them (or $\infty$ if no path exists). The diameter of a connected graph is $\max_{u,v} d(u,v)$ .

DefinitionSpecial Graphs

Complete graph $K_n$ : Graph with $n$ vertices where every pair is connected ( $|E| = \binom{n}{2}$ )
Cycle graph $C_n$ : Graph forming a single cycle of $n$ vertices
Path graph $P_n$ : Graph forming a single path of $n$ vertices
Bipartite graph: Vertices can be partitioned into two sets such that all edges connect vertices from different sets
Complete bipartite graph $K_{m,n}$ : Bipartite graph with parts of size $m$ and $n$ where all possible edges exist

Remark

Graph theory originated with Euler's 1736 solution to the Seven Bridges of Königsberg problem, which asked whether one could walk through the city crossing each bridge exactly once. Euler proved this impossible by modeling bridges as edges and landmasses as vertices, showing the problem required a path visiting every edge exactly once (an Eulerian path), which exists only if the graph has at most two odd-degree vertices. This problem launched graph theory as a mathematical discipline.

These foundational concepts enable precise analysis of network structures and relationship patterns across diverse applications.