A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A path is a sequence of distinct vertices where consecutive vertices are connected by edges. A cycle is a closed path where the first and last vertices are the same. A graph is connected if there is a path between every pair of vertices; otherwise it consists of multiple disconnected components. The distinction between walks (vertices may repeat), trails (edges do not repeat), and paths (vertices do not repeat) is essential. Connectivity is the foundational structural property for almost all graph-theoretic results.
Practice finding paths and cycles in small graphs by hand, writing out vertex sequences explicitly. Test connectivity by trying to reach every vertex from a fixed start. Deliberately construct examples that distinguish walks from trails from paths.
From your introduction to graphs, you know that a graph is a set of vertices and a set of edges connecting pairs of vertices. Now the natural question is: given two vertices, is there a way to travel from one to the other along edges? And if so, what kind of route is it? These questions lead to the core vocabulary of paths, cycles, and connectivity.
The vocabulary for routes through a graph comes in three levels of precision, and keeping them distinct is essential. A walk is completely permissive: you follow edges in sequence, and you may revisit any vertex or edge as many times as you like. A trail adds one restriction: you may not reuse any edge, though you may revisit vertices. A path is the most restrictive: you may not revisit any vertex, which automatically prevents reusing any edge. In formal notation, a path from u to v is a sequence u = v₀, v₁, ..., vₖ = v where all the vᵢ are distinct and each consecutive pair is connected by an edge.
A graph is connected if a path exists between every pair of vertices. If the graph is not connected, it decomposes into connected components — maximal subgraphs that are internally connected but have no edges between them. Checking connectivity from a given vertex can be done by a depth-first or breadth-first search: start at the vertex, follow edges to unvisited neighbors, repeat. If you reach every vertex, the graph is connected; if some vertices remain unreachable, they form separate components.
A very common misconception is that "no isolated vertices" implies connectivity. It does not. Isolated vertices have degree 0; removing them from the hypothesis still leaves graphs that are disconnected into multiple components, each of which has all its vertices connected to at least one other vertex within the component. Connectivity is a global property of the whole graph, not a local property of each vertex's neighborhood.
Cycles — closed paths where the first and last vertex coincide and all intermediate vertices are distinct — capture the idea of a loop in a graph. Cycles are central to almost every advanced graph theorem you will study next: trees are characterized as connected acyclic graphs, Euler circuits require every vertex to have even degree, and planarity is tied to the structure of cycles through Kuratowski's theorem. Keeping walks, trails, and paths precisely defined now will prevent errors when these theorems state exactly which type of route they are about.