Lesson 5

A graph is called connected if there is a path between every pair of its nodes. The nodes of any graph can be partitioned into connected components which are maximal connected subsets (that is, they are not contained in any larger connected subset).

For example, a graph \(G(V,E)\) with \[V=\{1, 2, 3, 4, 5, 6, 7\} \text{ and }E=\{\{2, 4\}, \{1, 7\}, \{2, 5\}, \{2, 6\}, \{4, 5\}, \{4, 6\}\}\] has three connected components: \(\{3\}\), \(\{2, 4, 6, 5\}\), and \(\{7, 1\}\). It is particularly easy to see this when the graph is drawn such that the three connected components are separated visually.