Graph Theory

Understanding Graph Theory

Graph theory is the study of structures made from “things” and the “connections” between them. The things are called vertices (or nodes), and the connections are called edges. Many problems in computer science, network design, social networks, transportation, and puzzles can be modeled using graphs.

This chapter introduces the core ideas of graph theory that you need before looking specifically at “Graphs” and “Trees” in their own chapters.

Basic Vocabulary

A graph $G$ consists of:

• a set of vertices (or nodes), usually written $V(G)$
• a set of edges, usually written $E(G)$

We write:
$$
G = (V, E)
$$
to mean “$G$ is a graph with vertex set $V$ and edge set $E$.”

An edge connects two vertices. In a simple picture-style graph, you draw dots (vertices) and lines between them (edges).

Types of edges

You will meet more detail in the later “Graphs” chapter, but here are the broad categories:

• Undirected edge: connects two vertices with no direction.
• Often drawn as a line between two vertices, like between $A$ and $B$.
• Directed edge (or arc): has a direction, from one vertex to another.
• Drawn with an arrow, from a tail vertex to a head vertex.

A graph with only undirected edges is an undirected graph.
A graph with directed edges is a directed graph (or digraph).

Sometimes edges can also carry extra information such as a cost, distance, or capacity. These are called weighted graphs. The number written on an edge is its weight.

Simple Graphs and Related Variants

There are many kinds of graphs. One very common kind is a simple graph.

A graph is called simple if:

• there is at most one edge between any pair of distinct vertices, and
• there are no edges from a vertex to itself.

If a graph can have:

• more than one edge between the same two vertices, it is called a multigraph.
• an edge that starts and ends at the same vertex, that edge is called a loop.

Simple graphs do not allow multiple edges or loops.

Degree of a Vertex

In an undirected graph, the degree of a vertex is the number of edges that touch that vertex.

If $v$ is a vertex, the degree of $v$ is written $\deg(v)$.

• If $v$ is connected to 3 other vertices, then $\deg(v) = 3$ (in a simple graph).
• If multiple edges or loops are allowed, each loop counts twice toward the degree (once for each “end” of the edge at the same vertex).

A vertex with degree 0 is called an isolated vertex. It has no edges.

Degree in directed graphs

In a digraph (directed graph), each vertex has:

• in-degree: number of edges coming into the vertex.
• out-degree: number of edges going out of the vertex.

These are written, for example, as:

• $\deg^-(v)$ for in-degree,
• $\deg^+(v)$ for out-degree.

Paths, Walks, and Cycles

Graph theory often studies ways of “moving” through the graph along edges.

Let $G=(V,E)$ be a graph.

• A walk is a sequence of vertices where each consecutive pair is joined by an edge.
• You are allowed to repeat vertices and edges.
• A path is a walk in which no vertex is repeated (except we sometimes allow the first and last to be the same in a special case, see cycles below).
• In many basic situations, “path” means a walk with all distinct vertices.
• A cycle in an undirected graph is a path that starts and ends at the same vertex and otherwise has no repeated vertices or edges.

For directed graphs, we talk about directed walks, directed paths, and directed cycles, where you must follow the direction of each edge.

Length

The length of a walk, path, or cycle is the number of edges it uses.

For example:

• A path that uses 4 edges has length 4.
• A cycle that goes around 3 edges has length 3.

Connectedness

Connectedness describes whether all vertices in a graph are reachable from each other.

In an undirected graph:

• A graph is connected if, for any two vertices $u$ and $v$, there is a path from $u$ to $v$.
• A graph that is not connected is called disconnected.

A connected component is a maximal connected subgraph: a part of the graph such that any two vertices in that part are connected by a path, and you cannot add any other vertex from the graph without losing this property.

In a directed graph, there are different notions:

• Strongly connected: for any two vertices $u$ and $v$, there is a directed path from $u$ to $v$ and also from $v$ to $u$.
• Weakly connected: if you ignore the directions on edges, the underlying undirected graph is connected.

These notions will reappear when you study directed graphs in more detail.

Subgraphs

A subgraph of a graph $G = (V, E)$ is another graph $H = (V_H, E_H)$ such that:

• $V_H \subseteq V$
• $E_H \subseteq E$

That is, a subgraph is formed by choosing some of the vertices and some of the edges from the original graph.

A spanning subgraph is a subgraph that uses all the vertices of the original graph (so $V_H = V$), but maybe not all of the edges.

A connected spanning subgraph that has no cycles is called a spanning tree of a connected graph (trees will be studied in their own chapter).

Special Types of Graphs

Certain graph structures appear so often that they have their own names.

Complete graphs

A complete graph on $n$ vertices, written $K_n$, is a simple undirected graph in which every pair of distinct vertices is connected by an edge.

• In $K_n$:
• Each vertex has degree $n-1$.
• There are $\dfrac{n(n-1)}{2}$ edges.

Complete graphs represent situations where every “thing” is connected to every other.

Bipartite graphs

A graph is bipartite if its vertices can be divided into two sets, say $A$ and $B$, such that:

• every edge connects a vertex in $A$ to a vertex in $B$, and
• there are no edges between two vertices both in $A$, and no edges between two vertices both in $B$.

Bipartite graphs are often used to model relationships between two different kinds of objects (for example, jobs and workers, customers and products).

A complete bipartite graph with parts of size $m$ and $n$ is denoted $K_{m,n}$. Every vertex in one part is connected to every vertex in the other part.

Regular graphs

A graph is $k$-regular if every vertex has the same degree $k$.

For example:

• A 3-regular graph has $\deg(v) = 3$ for every vertex $v$.

Regular graphs are often symmetric and appear in many combinatorial constructions.

Graph Isomorphism (Same Shape)

Two graphs can look different when drawn, yet really be the same in structure.

Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there is a one-to-one correspondence (a bijection) between their vertex sets that preserves edges.

Informally:

• You can “rename” the vertices of $G_1$ to get $G_2$.
• After renaming, the adjacency (which vertices are joined by edges) is exactly the same.

Graph isomorphism is how we formalize the idea that two graphs have the same shape, even if drawn differently.

Planar Graphs and Graph Drawings

Graphs are often drawn on a plane (a flat piece of paper).

A graph is planar if it can be drawn in the plane with edges as curves such that:

• edges only intersect at their endpoints (no crossings in the middle of edges).

If a graph can be drawn with no edges crossing, it has a planar embedding.

Planar graphs are connected to maps, regions, and famous results like Euler’s formula for planar graphs, which relates the number of vertices, edges, and faces in such a drawing.

Graph Coloring

A vertex coloring of a graph assigns a “color” (or label) to each vertex so that:

• no two adjacent vertices (connected by an edge) share the same color.

The smallest number of colors needed for such a coloring is called the graph’s chromatic number, often written $\chi(G)$.

Graph coloring is used in scheduling problems, map coloring, and resource allocation, where “colors” represent limited resources that cannot be shared by conflicting items.

Graph Theory and Algorithms

Graph theory is deeply linked with algorithms.

Graphs provide a way to model:

• networks (computer networks, roads, social networks),
• optimization problems (shortest path, minimal cost routes),
• matching problems (pairing items under constraints),
• and many more.

Some famous algorithmic problems in graph theory include:

• finding a shortest path between two vertices,
• finding a spanning tree with minimal total weight (minimum spanning tree),
• determining whether a graph has a cycle through all vertices (Hamiltonian cycle),
• or whether there is a path that uses each edge exactly once (Eulerian path).

Specific algorithms and their details belong to more advanced or specialized chapters, but the modeling step—translating a real-world problem into a graph—is a core skill introduced here.

Summary

Graph theory studies:

• vertices and edges, and how they form structures called graphs;
• fundamental properties such as degrees, paths, cycles, and connectedness;
• special kinds of graphs: complete, bipartite, regular, planar, and others;
• structural equivalence via graph isomorphism;
• coloring and other combinatorial properties;
• and provides the language and tools for modeling a wide range of discrete problems.

Later chapters “Graphs” and “Trees” will delve deeper into particular structures and their more precise properties and theorems.