Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Walk and Path
Definitions from the module sheet, for a graph and vertices :
- a walk from to is an alternating sequence with , and each edge joining and
- the length of a walk is (the number of edges), or the sum of edge weights if is weighted
- a path is a walk that does not pass through any vertex twice
- a cycle is a walk that starts and ends at the same vertex and passes through no other vertex twice, so no edge is repeated
Example: is a cycle, but is not, because it reuses edge .

Subgraph
is a subgraph of if every vertex and every edge of is also in , i.e. and .
Connectivity
Definitions:
- and are connected if there is a walk (equivalently a path) between them, since any walk that repeats a vertex can be shortened into a path
- a graph is connected if every pair of distinct vertices is connected, otherwise it is disconnected
- a connected component is a connected subgraph that cannot be extended to a larger connected subgraph
- a graph has exactly one component if and only if it is connected
Trees in Graph Theory
A tree is a connected graph with no cycles. A tree with vertices always has edges (proof not required). A rooted tree is a tree in this sense, with one edge from each node to each of its children.

From left to right: the first graph is not a tree because form a cycle, and the last is not a tree because vertex is not connected. Trees lead directly to Spanning Trees.
Distance and Shortest Path
In a weighted undirected graph with non-negative weights, the distance from to is the minimum length of a path from to ( if there is none), and a shortest path is a path with that length.