10.1 Basic concepts and definitions in graph theory

Graph theory gives you a precise language for describing networks and relationships between objects. Whether you're modeling social connections, transportation routes, or data structures, the same core concepts apply. This section covers the building blocks: vertices, edges, graph types, degree properties, and connectivity.

Graph Components

Fundamental Elements of Graphs

A graph is a structure made up of two things: a set of points and a set of connections between them.

• A vertex (plural: vertices) is a point or node in a graph. Vertices represent entities like cities, people, or data points.
• An edge is a connection between two vertices, drawn as a line or arc. Edges represent relationships: friendships, roads, links.

Every graph is formally written as $G = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges. When you draw a graph, vertices are dots and edges are lines connecting them.

Graph Characteristics and Classifications

• The order of a graph is $|V|$, the number of vertices.
• The size of a graph is $|E|$, the number of edges.
• A loop is an edge that connects a vertex to itself. Multiple edges (also called parallel edges) are two or more edges connecting the same pair of vertices.
• A simple graph has no loops and no multiple edges. Most of the graphs you'll work with in this course are simple graphs unless stated otherwise.
• A multigraph allows loops and/or multiple edges between the same pair of vertices.

Graphs can be stored in two common ways: an adjacency matrix (a square matrix where entry $(i,j)$ is 1 if vertices $i$ and $j$ are connected, 0 otherwise) and an adjacency list (each vertex stores a list of its neighbors). Adjacency lists tend to be more space-efficient for sparse graphs; adjacency matrices make it fast to check whether a specific edge exists.

Directed vs Undirected Graphs

Undirected Graphs

In an undirected graph, edges have no direction. If there's an edge between vertices $u$ and $v$, you can traverse it either way. These are drawn as plain lines without arrows.

Undirected graphs model symmetric relationships. A friendship network is a classic example: if Alice is friends with Bob, then Bob is friends with Alice.

Directed Graphs

In a directed graph (or digraph), each edge has a specific direction, drawn as an arrow from one vertex to another. These directed edges are sometimes called arcs.

Because direction matters, each vertex has two separate degree counts:

• In-degree: the number of edges pointing into the vertex
• Out-degree: the number of edges pointing out of the vertex

Digraphs model asymmetric relationships. Think of social media follows: you can follow someone without them following you back. Other examples include one-way streets and network traffic flow.

Mixed Graphs

A mixed graph contains both directed and undirected edges. These come up when modeling systems that have both symmetric and asymmetric relationships, like a city's road network with a mix of one-way and two-way streets.

Vertex Properties

Adjacency and Incidence

Two vertices are adjacent if they're directly connected by an edge. An edge is incident to a vertex if that vertex is one of the edge's endpoints.

These relationships can be captured in matrix form:

• An adjacency matrix is an $n \times n$ matrix (where $n = |V|$) recording which vertices are connected to which.
• An incidence matrix is a $|V| \times |E|$ matrix recording which vertices are endpoints of which edges.

Vertex Degree

The degree of a vertex is the number of edges incident to it. A few special cases worth knowing:

• An isolated vertex has degree 0 (no connections at all).
• A leaf (or pendant vertex) has degree 1 (exactly one connection).

For directed graphs, the total degree of a vertex equals its in-degree plus its out-degree.

The Handshaking Lemma is one of the first important results in graph theory:

Why twice? Because every edge contributes exactly 1 to the degree of each of its two endpoints. A direct consequence: the number of vertices with odd degree must be even.

Paths, Cycles, and Connectivity

Paths and Cycles

A path is a sequence of distinct vertices where each consecutive pair is connected by an edge. The length of a path is the number of edges in it (not vertices).

A cycle is a path that starts and ends at the same vertex, with no other repeated vertices. A cycle must have length at least 3 in a simple graph.

Two famous types of traversals show up frequently:

• An Eulerian path traverses every edge exactly once. It exists if and only if the graph is connected and has exactly 0 or 2 vertices of odd degree.
• A Hamiltonian path visits every vertex exactly once. Unlike Eulerian paths, there's no simple necessary-and-sufficient condition for when these exist, which is part of what makes them computationally harder.

Graph Connectivity

Connectivity describes whether you can get from any vertex to any other by following edges.

• A graph is connected if there's a path between every pair of vertices.
• A component is a maximal connected subgraph. If a graph isn't connected, it breaks into two or more components.
• A bridge is an edge whose removal disconnects the graph (or increases the number of components).
• An articulation point (or cut vertex) is a vertex whose removal increases the number of components.

For directed graphs, connectivity gets more nuanced. A digraph is strongly connected if, for every pair of vertices $u$ and $v$, there's a directed path from $u$ to $v$ and from $v$ to $u$. If you can only guarantee paths when you ignore edge directions, the digraph is weakly connected.