Lesson 6

We now turn to formal definitions. Two nodes of an undirected graph are called connected, if there is a path between them. This property is transitive: if \(u\) and \(v\) are connected and \(v\) and \(w\) are connected, then \(u\) and \(w\) are connected, too: indeed, the two paths can be combined into one. A graph is connected, if any two of its nodes are connected. In other words, there is a path between any two of its nodes.

The nodes of any undirected graph can be partitioned into subsets called connected components satisfying the following properties:

• any node belongs to exactly one connected component;


• any two nodes from the same connected component are connected;


• any two nodes from different connected components are not connected.

To give an example, recall the following graph. It has two connected components: \(\{5, 1, 2\}\) and \(\{3, 4, 8, 7, 6\}\).

from networkx import connected_components, Graph

edges = [(1, 2), (3, 8), (4, 6), (3, 6), (2, 5), (3, 7), (4, 8), (5, 1)]
print(list(connected_components(Graph(edges))))

[{1, 2, 5}, {3, 4, 6, 7, 8}]