Graph minor

Remarks

Equivalently, there are pairwise disjoint nonempty sets $B_x \subseteq V(G)$, one for each vertex $x$ of $H$, with two properties. Each $B_x$ induces a connected subgraph of $G$. For each edge $xy$ of $H$, some edge of $G$ joins $B_x$ to $B_y$. The sets $B_x$ are called branch sets. Example: $K_5$ is a minor of the Petersen graph. Take as branch sets the five spokes, each made of an outer vertex and its inner neighbour. Then the outer $5$-cycle and the inner pentagram join every two branch sets. Non-example: the triangle $K_3$ is not a minor of any tree, because deleting and contracting edges of a forest always gives a forest. Every subgraph is a minor, but a minor need not be a subgraph. For example, $K_3$ is a minor of every cycle $C_n$ with $n \ge 3$ but a subgraph only of $C_3$.