Exercise 470Combinatorics › Graph theoryHigh schoolAdded 3 Nov 2026

Connected components

#connectivity#connected components

Statement

Determine the number of connected components of the graph with vertices $\{1,\ldots,7\}$ and edges $\{1,2\},\{2,3\},\{4,5\},\{6,7\},\{5,6\}$ .

Hint

Find maximal connected subgraphs.

Show solutionHide solution

Component 1. $\{1,2,3\}$ : path $1$ - $2$ - $3$ .

Component 2. $\{4,5,6,7\}$ : path $4$ - $5$ - $6$ - $7$ .

Count. $2$ components.

Conclusion. The graph has $2$ connected components.