The result of a sequence of such identifications is a contraction . Thus, the triangle pictured above is a contraction of the square. We can picture all the contractions of a graph together, ordered by the order in which the identifications happened. G is said to induce a subgraph H of G if H has S as its vertex set, and it has an edge between two elements of S precisely if G does. A graph G is connected if there is a path from any vertex to any other vertex along edges of G .
G is a splitting up of the vertices of G into sets, each of which induces a connected subgraph.
Order them by set inclusion. Let T n be any tree on n vertices, that is, any graph on n vertices that has no cycles. K n is the graph on n vertices, where every two vertices are connected by an edge. For example, K 3 looks like a triangle, and K 4 looks like a pyramid. It's the Stirling numbers of the second kind.