Mathwords logoMathwords

Path Graph — Definition, Formula & Examples

A path graph is a graph consisting of a sequence of vertices connected end-to-end by edges, forming a single chain with no branches or cycles.

The path graph PnP_n on nn vertices is a tree with vertex set {v1,v2,…,vn}\{v_1, v_2, \ldots, v_n\} and edge set {{vi,vi+1}:1≤i≤n−1}\{\{v_i, v_{i+1}\} : 1 \le i \le n-1\}. It has exactly n−1n - 1 edges, and precisely two vertices of degree 1 (the endpoints) while all interior vertices have degree 2.

Key Formula

∣E(Pn)∣=n−1|E(P_n)| = n - 1
Where:
  • PnP_n = The path graph on n vertices
  • nn = Number of vertices (n ≥ 1)
  • ∣E(Pn)∣|E(P_n)| = Number of edges in the path graph

Worked Example

Problem: Consider the path graph P5P_5. Determine its edges, its degree sequence, and verify whether it is a tree.
Step 1: List the vertices and edges. P5P_5 has vertices v1,v2,v3,v4,v5v_1, v_2, v_3, v_4, v_5 connected in a chain.
E={{v1,v2},{v2,v3},{v3,v4},{v4,v5}}E = \{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_4\},\{v_4,v_5\}\}
Step 2: Find the degree of each vertex. The two endpoints have degree 1, and the three interior vertices each have degree 2.
deg⁡(v1)=1,  deg⁡(v2)=2,  deg⁡(v3)=2,  deg⁡(v4)=2,  deg⁡(v5)=1\deg(v_1)=1,\;\deg(v_2)=2,\;\deg(v_3)=2,\;\deg(v_4)=2,\;\deg(v_5)=1
Step 3: Check the tree conditions: a tree on nn vertices has exactly n−1n-1 edges and is connected with no cycles. Here ∣E∣=4=5−1|E|=4=5-1, the graph is connected, and it contains no cycles.
∣E∣=5−1=4✓|E| = 5 - 1 = 4 \quad \checkmark
Answer: P5P_5 has 4 edges, degree sequence (1,2,2,2,1)(1, 2, 2, 2, 1), and is indeed a tree.

Why It Matters

Path graphs serve as a baseline case in proofs and algorithms throughout graph theory and combinatorics. Many properties — chromatic number, independence number, Hamiltonian paths — are easy to verify on PnP_n, making it a standard test case. They also model real structures like linear pipelines and sequential processes in computer science.

Common Mistakes

Mistake: Confusing a path graph PnP_n with a cycle graph CnC_n.
Correction: A path graph has two endpoints of degree 1 and no cycles, while a cycle graph closes the chain into a loop so every vertex has degree 2. PnP_n has n−1n-1 edges; CnC_n has nn edges.

Related Terms