Introduction to Graph Theory - Part 3

In the previous part, we introduced the basic building blocks of graph theory: vertices, edges, adjacency, and degree. With these tools in hand, we can now explore different types of graphs that show up frequently in theory and practice. Think of it like learning about different shapes in geometry — once you know what a triangle or a circle is, you can start recognizing them everywhere.

Subgraphs

Before we look at specific graph classes, let's first talk about a concept that will come in handy throughout this series. Sometimes, we don't want to consider an entire graph, but only a part of it. For instance, think of our friendship graph from Part 2 — maybe we want to focus on just a few people and the friendships between them. This leads us to the idea of a subgraph.

Definition 4. A graph $H = (V_H, E_H)$ is a subgraph of a graph $G = (V, E)$ if $V_H \subseteq V$ and $E_H \subseteq E$.

In other words, a subgraph is obtained by selecting some vertices and some edges from the original graph, as long as the selected edges only connect selected vertices. There is also a more specific notion: if we pick a subset of vertices and keep all edges between them, we get a special kind of subgraph.

Definition 5. Let $G = (V, E)$ be a graph and $S \subseteq V$. The induced subgraph $G[S]$ is the graph $(S, E_S)$, where $E_S = \{(u, v) \in E \mid u \in S \text{ and } v \in S\}$.

To make this concrete, consider the graph $G = (\{1,2,3,4\}, \{(1,2), (1,3), (2,3), (3,4)\})$. If we take $S = \{1,2,3\}$, the induced subgraph $G[S]$ contains the vertices $\{1,2,3\}$ and the edges $\{(1,2), (1,3), (2,3)\}$ — notice that the edge $(3,4)$ is not included because vertex $4$ is not in $S$.

Complete Graphs

Let's go back to our friendship example. Imagine a group of people where everyone is friends with everyone else. No one is left out — every possible pair of people has a direct connection. This gives us a very special type of graph called a complete graph.

Definition 6. A complete graph on $n$ vertices, denoted $K_n$, is a graph where every pair of distinct vertices is connected by an edge.

The smallest interesting complete graph is $K_3$, which is just the triangle graph we saw in Part 2. Next comes $K_4$, a graph on four vertices where each vertex is connected to every other vertex, giving us $6$ edges in total.

In general, $K_n$ has exactly $\binom{n}{2} = \frac{n(n-1)}{2}$ edges. This follows directly from the fact that we need to choose $2$ vertices out of $n$ to form each edge. We can also verify this using the degree: in $K_n$, every vertex has degree $n-1$, so the sum of all degrees is $n(n-1)$. Since each edge contributes exactly $2$ to the total degree sum¹, we get $m = \frac{n(n-1)}{2}$ edges.

Paths and Cycles

In Part 1, we talked about Euler walking across bridges. But what does it actually mean to "walk" through a graph? Let's make this precise. A path is a sequence of distinct vertices where each consecutive pair is connected by an edge — in other words, you move from one vertex to the next without ever visiting the same vertex twice.

Definition 7. A path graph $P_n$ is a graph on $n$ vertices $\{v_1, v_2, \ldots, v_n\}$ with edges $\{(v_1, v_2), (v_2, v_3), \ldots, (v_{n-1}, v_n)\}$.

The path $P_3$, for example, consists of three vertices in a line: $v_1 - v_2 - v_3$. The first and last vertex each have degree $1$, while the middle vertex has degree $2$.

Now, what happens if the person walking through the graph ends up exactly where they started? If we take a path and connect the last vertex back to the first, we get a cycle.

Definition 8. A cycle graph $C_n$ is a graph on $n$ vertices $\{v_1, v_2, \ldots, v_n\}$ with edges $\{(v_1, v_2), (v_2, v_3), \ldots, (v_{n-1}, v_n), (v_n, v_1)\}$.

The smallest cycle is $C_3$, which is the triangle — so $C_3$ is the same graph as $K_3$. In a cycle $C_n$, every vertex has degree exactly $2$, since each vertex is connected to its predecessor and its successor.

Observation 2. A path $P_n$ has $n-1$ edges, and a cycle $C_n$ has $n$ edges.

This is easy to see: a path connects $n$ vertices with one edge between each consecutive pair, giving $n-1$ edges. A cycle does the same but adds one more edge to close the loop.

Bipartite Graphs

So far, we've looked at graphs where any vertex can be connected to any other. But in many real-world scenarios, connections only exist between two distinct groups. Think of students and courses at a university: students are enrolled in courses, but a student isn't "connected" to another student in this context, and a course isn't connected to another course. The edges only go between the two groups.

Definition 9. A graph $G = (V, E)$ is called bipartite if its vertex set can be partitioned into two disjoint sets $A$ and $B$ (with $V = A \cup B$ and $A \cap B = \emptyset$) such that every edge connects a vertex in $A$ to a vertex in $B$.

Consider the graph $G = (\{1,2,3,4\}, \{(1,3), (1,4), (2,3)\})$ with $A = \{1, 2\}$ and $B = \{3, 4\}$. Every edge goes from a vertex in $A$ to a vertex in $B$, so this graph is bipartite. Notice that there are no edges within $A$ or within $B$.

Just as we have complete graphs where every possible edge is present, we can define a complete bipartite graph where every vertex in $A$ is connected to every vertex in $B$.

Definition 10. The complete bipartite graph $K_{a,b}$ is a bipartite graph with $|A| = a$ and $|B| = b$, where every vertex in $A$ is adjacent to every vertex in $B$.

The complete bipartite graph $K_{a,b}$ has exactly $a \cdot b$ edges, since each of the $a$ vertices on one side is connected to all $b$ vertices on the other side. For example, $K_{2,3}$ has $6$ edges connecting $2$ vertices on one side to $3$ vertices on the other.

Trees

Trees are among the most important structures in all of graph theory and computer science. You've probably encountered them before — file systems on your computer, organizational hierarchies, and family trees all have the same underlying structure. A tree is a graph that is connected (you can reach any vertex from any other) but contains no cycles.

Definition 11. A tree is a connected graph that contains no cycle as a subgraph.

The simplest tree is a single vertex with no edges. The next is a single edge connecting two vertices — which is also the path $P_2$. In fact, every path graph $P_n$ is a tree, since paths are connected and don't contain any cycles.

Let's check: the graph $G = (\{1,2,3,4\}, \{(1,2), (1,3), (1,4)\})$ is a tree. It is connected (every vertex can be reached from vertex $1$) and contains no cycle. This particular tree has a special shape — vertex $1$ is connected to all others, forming a star.

Observation 3. A tree on $n$ vertices has exactly $n-1$ edges.

We can convince ourselves of this by thinking about it inductively. A single vertex has $0$ edges. Each time we add a new vertex to the tree, we need exactly one edge to connect it to the existing tree — if we added more than one edge, we would create a cycle, and if we added none, the vertex would be disconnected. So after adding $n-1$ vertices to the initial one, we have exactly $n-1$ edges².

Regular Graphs

Let's return once more to our friendship analogy. In most social networks, different people have different numbers of friends. But what if everyone in a group had exactly the same number of friends? This gives us a very symmetric type of graph.

Definition 12. A graph $G$ is called $k$-regular if every vertex has degree $k$.

We've already seen several examples of regular graphs without realizing it. The cycle $C_n$ is $2$-regular, since every vertex has degree $2$. The complete graph $K_n$ is $(n-1)$-regular, since every vertex is connected to all $n-1$ other vertices. And the complete bipartite graph $K_{a,a}$ (with equal-sized parts) is $a$-regular.

A particularly famous example is the Petersen graph, which is $3$-regular and has $10$ vertices and $15$ edges. It serves as an important counterexample in many areas of graph theory and shows up surprisingly often³.

Looking Ahead

Now that we have a toolbox of graph classes, we can start asking more interesting questions. How do we move through a graph? When is a graph "connected"? Can we always find a path between two vertices? In the next part, we will explore walks, paths, and the concept of connectivity — building directly on the definitions we've established so far.