Định lí 7. Giữa mọi cặp đỉnh phân biệt của một đồ thị liên thông luôn có đường đi sơ cấp.
Đường đi sơ cấp bạn đọc xem ở mục định nghĩa 1.8 về tính liên thông của đồ thị
Chứng minh Giả sử $u$ và $v$ là hai đỉnh phân biệt của một đồ thị liên thông $G$. Vì $G$ liên thông nên có ít nhất một đường đi giữa $u$ và $v$. Gọi $x_0, x_1, ..., x_n$, với $x_0=u$ và $x_n=v$, là dãy các đỉnh của đường đi có độ dài ngắn nhất. Đây chính là đường đi sơ cấp cần tìm. Thật vậy, giả sử nó không là đường đi đơn, khi đó $x_i=x_j$ với $0 \le i < j$. Điều này có nghĩa là giữa các đỉnh $u$ và $v$ có đường đi ngắn hơn qua các đỉnh $x_0, x_1, ..., x_{i-1}, x_j, ..., x_n$ nhận được bằng cách xoá đi các cạnh tương ứng với dãy các đỉnh $x_i, ..., x_{j-1}$.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]