Given a graph with vertex set \({ V }\) we can define a relation \({ S }\) on \({ V }\) by saying that \({ ( v , w ) ∈ S }\) if \({ v = w }\) or there is a walk with initial vertex \({ v }\) and final vertex \({ w }\). This is a reflexive relation, because we defined \({ ( v , w ) ∈ S }\) to be true if \({ v = w }\). It is also a transitive relation. In other words, if \({ ( u , v ) ∈ S }\) and \({ ( v , w ) ∈ S }\) then \({ ( u , w ) ∈ S }\). If \({ u = v }\) then \({ ( u , w ) }\) and \({ ( v , w ) }\) are the same, so it’s clear that if \({ ( v , w ) ∈ S }\) then \({ ( u , w ) ∈ S }\). Similarly if \({ v = w }\) then \({ ( u , v ) }\) and \({ ( u , w ) }\) are the same, so if \({ ( u , v ) ∈ S }\) then \({ ( u , w ) ∈ S }\). The only interesting case is therefore the one where there is a walk from \({ u }\) to \({ v }\) and a walk from \({ v }\) to \({ w }\). In this case we can obtain a walk from \({ u }\) to \({ w }\) by concatenating the list of edges in the walk from \({ u }\) to \({ v }\) and the list of edges in the walk from \({ v }\) to \({ w }\).
If the relation \({ S }\) is antisymmetric then we say the graph is a directed acyclic graph. In this case the set of vertices with the relation \({ S }\) form a partially ordered set.
A tree is just a directed acyclic graph in which there is at most one walk from any vertex to any other vertex. In the theory of undirected graphs we say that a graph is a tree if it’s connected and has no simple circuit of length greater than two. These two seemingly different definitions are related as follows. An undirected graph is a tree, as defined for undirected graphs, if and only if its possible to choose a direction for each edge making it into a tree, as defined for directed graphs.
If the graph is undirected then \({ S }\) is symmetric, since we can then obtain a walk from \({ v }\) to \({ w }\) from a walk from \({ w }\) to \({ v }\) by reversing the order of the edges in the walk and reversing the direction of each edge. So in this case the relation \({ S }\) is an equivalence relation. The equivalence classes are called connected components. A non-empty undirected graph is called connected if it has only one connected component, i.e. if for every two distinct vertices there is a walk connecting them. All of the undirected graphs which have appeared so far are connected, except for the EU border graph, which has five connected components. One each with just Cyprus, Ireland and Malta as members, one with just Finland and Sweden, and one with all other EU states as members.
If two distinct vertices belong to the same equivalence class then there is a walk between them. Lengths of walks are natural numbers so there must then be a shortest walk. If this walk had a vertex which appeared more than once then we could further shorten it by removing all the edges between its first appearance and its last, but then it wouldn’t be a shortest walk, so there can be no repeated vertices. In other words the walk is a path. We already knew from the definition that any two vertices in a connected component are connected by a walk but the argument above shows that they are in fact connected by a path. This is a stronger statement since every path is a walk but not every walk is a path. It would have been a bad idea to define connected components in terms of paths though since this would have made it harder to prove the transitivity property.