Let's begin with some problems for which there are polynomial-time algorithms. Suppose you are given a graph on $n$ vertices and asked whether or not the graph is connected. Here a positive answer can be justified by providing a spanning tree. On the other hand, a negative answer can be justified by providing a partition of the vertex sets $V=V_1\cup V_2$ with $V_1$ and $V_2$ non-empty subsets and having no edges with one end-point in $V_1$ and the other in $V_2\text{.}$ In Chapter 12 we will discuss two efficient algorithms that find spanning trees in connected graphs. They can easily be modified to produce a partition showing the graph is disconnected.