Degree, Paths, and Cycles in Graph Theory

Welcome, students, to one of the most important early lessons in graph theory 📘. In this lesson, you will learn how to describe connections in a graph using degree, paths, and cycles. These ideas show up everywhere: social networks, road maps, computer networks, and even puzzle games. By the end, you should be able to explain the main terms, work through examples, and recognize how these ideas connect to the bigger picture of Midterm 1 and Intro to Graph Theory.

What Graph Theory Is Really About

Graph theory studies graphs, which are mathematical models of objects and the connections between them. A graph has vertices (also called nodes) and edges (also called links or lines). Think of a map of cities and roads: the cities are vertices, and the roads are edges 🚗.

To understand a graph, one of the first questions we ask is: how many connections does each vertex have? That leads to degree. Another question is: can we travel from one place to another by following edges? That leads to paths. Finally, can we travel and end up back where we started? That leads to cycles.

These ideas are not just vocabulary. They help us reason about networks, analyze structures, and solve problems in discrete mathematics.

Degree: Counting How Many Edges Touch a Vertex

The degree of a vertex is the number of edges incident to it. In simple terms, it tells you how many connections a vertex has.

If a vertex is labeled $v$, its degree is written as $\deg(v)$.

For example, suppose a vertex is connected to three other vertices by three edges. Then its degree is $\deg(v)=3$.

Example 1: Friend Network

Imagine a small group chat where students can message three classmates directly. In a graph, students would be a vertex, and each direct connection would be an edge. If students has three direct connections, then $\deg(\text{students})=3$.

That is a simple real-world way to think about degree: it measures how connected something is.

Important Degree Facts

In an undirected graph, every edge contributes $1$ to the degree of each endpoint.
A vertex can have degree $0$ if it is isolated, meaning no edges touch it.
A loop is an edge that starts and ends at the same vertex. In many graph theory courses, a loop contributes $2$ to the degree of that vertex because it touches the vertex twice.

Degree Example

Suppose a graph has vertices $A$, $B$, $C$, and $D$, with edges $AB$, $AC$, $AD$, and $CD$.

$\deg(A)=3$
$\deg(B)=1$
$\deg(C)=2$
$\deg(D)=2$

Why? Because each degree is the number of edges touching the vertex.

Handshaking Idea

In an undirected graph, the sum of all vertex degrees equals twice the number of edges:

$$\sum \deg(v)=2|E|$$

This works because every edge has two endpoints, so it gets counted twice. This fact is often called the Handshaking Lemma 🤝.

For example, if a graph has $5$ edges, then the sum of all degrees must be $2\cdot 5=10$.

This is useful for checking whether a proposed graph is possible.

Paths: Moving Step by Step Through a Graph

A path is a sequence of vertices where each consecutive pair is connected by an edge. A path shows a way to move through the graph.

If the vertices are $v_0, v_1, v_2, \dots, v_k$, then a path is written as

$$v_0,v_1,v_2,\dots,v_k$$

where each edge $v_i v_{i+1}$ exists.

The length of a path is the number of edges in it. A path with vertices $v_0$ through $v_k$ has length $k$.

Example 2: City Travel

Suppose you travel from city $A$ to city $B$, then to city $D$, then to city $F$. If each of those steps uses a road, then $A,B,D,F$ is a path of length $3$.

In graph language, you are not teleporting. You are moving edge by edge.

Simple and Repeated Vertices

A path is called simple if it does not repeat vertices. Some textbooks make a distinction between a path and a walk:

A walk may repeat vertices and edges.
A path usually means a walk with no repeated vertices.

Because different classes use slightly different conventions, students should follow the definitions used in your course notes. In many intro discrete math classes, the key idea is that a path connects vertices by following edges in order.

Why Paths Matter

Paths help answer questions like:

Can one vertex reach another?
What is the shortest route?
Is the graph connected?

If there is a path between every pair of vertices in a graph, the graph is called connected. That means there are no isolated “separate islands” in the network.

Example 3: Connectivity Check

Suppose vertices $A$, $B$, and $C$ are connected in a chain $A-B-C$. Then there is a path from $A$ to $C$, namely $A,B,C$.

But if another vertex $D$ has no edges, then there is no path from $A$ to $D$. The graph is not connected.

This kind of reasoning is a major skill in graph theory: looking at the edges and deciding whether movement is possible.

Cycles: Paths That Return to the Start

A cycle is a path that starts and ends at the same vertex, with no repeated edges and usually no repeated vertices except the starting/ending vertex.

In notation, a cycle may look like

$$v_0,v_1,v_2,\dots,v_{k-1},v_0$$

This means you begin at $v_0$, travel through several vertices, and return to $v_0$.

Example 4: Triangle Cycle

A triangle graph with vertices $A$, $B$, and $C$, and edges $AB$, $BC$, and $CA$, contains a cycle:

$$A,B,C,A$$

That is a cycle of length $3$.

Real-World Example

Think of a circular bike path around a park 🚴. If you start at one point, follow the path around, and return to the same point, you have traced a cycle.

Cycle vs. Path

A path is about getting from one vertex to another. A cycle is about making a loop and coming back to where you started.

This distinction matters because cycles often show structure in a network. For example, a cycle can mean there is more than one way to travel between locations, which can be important in road systems and computer networks.

Putting Degree, Paths, and Cycles Together

These three ideas work together.

Degree tells us how many connections a vertex has.
Paths tell us how to move through the graph.
Cycles tell us when a route loops back to the start.

Example 5: Small Graph Analysis

Consider a graph with vertices $P$, $Q$, $R$, and $S$ and edges $PQ$, $QR$, $RS$, and $SP$.

$\deg(P)=2$
$\deg(Q)=2$
$\deg(R)=2$
$\deg(S)=2$

There are paths such as $P,Q,R$ and $Q,R,S$.

There is also a cycle:

$$P,Q,R,S,P$$

This graph is a square, so every vertex has degree $2$, and the graph contains a cycle of length $4$.

How Midterm Problems Often Look

In Midterm 1, you may be asked to:

identify the degree of a vertex from a diagram,
list a path between two vertices,
determine whether a graph contains a cycle,
compute the sum of all degrees,
use the Handshaking Lemma to check an answer.

These problems test both vocabulary and reasoning. You are not just memorizing terms; you are reading a structure and drawing conclusions from it.

Reasoning Strategy

When solving graph theory questions, try this order:

Identify the vertices and edges.
Count the degree of each vertex.
Look for possible paths between vertices.
Check whether any path returns to its start and forms a cycle.
Use the Handshaking Lemma if needed to verify your work.

This step-by-step process helps prevent counting mistakes.

Conclusion

Degree, paths, and cycles are core ideas in intro graph theory. Degree measures how connected a vertex is. Paths describe routes through a graph. Cycles describe routes that return to the starting vertex. Together, these ideas help you analyze networks, solve Midterm 1 problems, and build the foundation for later topics in discrete mathematics.

If students can recognize these three ideas in a graph, then many bigger problems become much easier. The skill is not only knowing the definitions, but also using them to explain what is happening in a graph and why.

Study Notes

A graph has vertices and edges.
The degree of a vertex $v$ is written $\deg(v)$ and means the number of edges incident to $v$.
In an undirected graph, the sum of all degrees is $2|E|$.
A path is a sequence of vertices where consecutive vertices are connected by edges.
The length of a path is the number of edges in it.
A graph is connected if there is a path between every pair of vertices.
A cycle is a path that starts and ends at the same vertex.
A triangle is a cycle of length $3$.
Degree helps measure connectivity, paths help describe travel, and cycles help identify loops in a graph.
These concepts are common in Midterm 1 questions and are essential for Intro to Graph Theory 📊.