The independent set I and remainder F

PDF p. 3: Section 3, paragraph beginning Assume without loss

Let $H_1$ and $H_2$ be non-isomorphic finite connected simple graphs, each with an edge, labelled so that $\beta (H_1)\ge \beta (H_2)$ and, if equality holds, $\mathrm{\mid }{H}_1\mathrm{\mid }\ge \mathrm{\mid }{H}_2\mathrm{\mid }$. Here $\mathrm{\mid }H\mathrm{\mid }$ is the number of vertices of $H$. A graph is connected when every two vertices are joined by a path. A block is a maximal 2-connected subgraph, or a bridge together with its endpoints. A 2-connected graph has at least three vertices, is connected, and remains connected after deletion of any one vertex; a bridge is an edge whose deletion increases the number of connected components. For a nonempty graph with an edge, $\beta$ is the largest number of vertices in a block, and for a nonempty edgeless graph it is $1$.

Choose an independent set $I\subseteq V(H_2)$ such that $\beta (H_2-I)<\beta (H_2)$, and set $F=H_2-I$. Independent means that no edge of $H_2$ has both endpoints in $I$. The graph $H_2-I$ is induced on $V(H_2)\setminus I$: it has exactly the edges of $H_2$ with both endpoints remaining. Thus $F$ is nonempty and $\beta (F)<\beta (H_2)\le \beta (H_1)$. The choice of $I$ is fixed for subsequent constructions; it need not be unique.

The graph and block definitions make the hypotheses, ordering and parameter definite. The target-ordering result permits this labelling for the stated pair. The independent-deletion result supplies an independent set with the required strict inequality because $H_2$ is finite, connected and has an edge. Since an independent set cannot contain both endpoints of an edge, the nonempty-remainder result ensures that $H_2-I$ has a vertex. Vertex deletion then determines $F$ as the indicated induced graph, so $\beta (F)$ is defined; combining the strict inequality with the chosen ordering gives the displayed chain. Fixing any one eligible $I$ defines the data without asserting uniqueness. The path supplier defines the paths used in connectedness as finite lists of distinct vertices with an edge between each consecutive pair, allowing a one-vertex path. Graph and colouring conventions Blocks and the parameter beta Ordering targets and excluding H1 from H2 Independent deletion decreases beta Nonempty remainder after deleting an independent set Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors Cliques, independent sets, clique number and independence number Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges

Graph and colouring conventions

Blocks and the parameter beta

Cliques, independent sets, clique number and independence number

Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors

Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges