Prove that if a graph $G$ has a Hamilton path then for every $S \subseteq V(G)$ the number of components of $G - S$ is at most $|S| + 1$.
I have tested this numerically with some examples and can picture why this works but I am unsure how I would go about proving this mathematically. Any help is appreciated.
On
Consider the Hamiltonian path $P$ in $G$. By deleting the $|S|$ vertices in $S$ we split the path into at most $|S| + 1$ smaller paths. Obviously each vertex in $G-S$ is in one such path, so we have at most $|S| + 1$ connected components.
On
I hope it can help you
Suppose the components of $G - S$ are $C_1,C_2,...,C_k$.
$G$ has a hamiltonian path so a hamiltonian path in G must cover all vertices, it must go to each of the components of $G − S$.
To go from one component to another, there must be one vertex in S traversed in between (as there is no direct path between two components of $G − S$).
Hence the maximum number of components can only be $|S| + 1$ (happens when the two endpoints of the ham path are outside of $S$).
First, consider the case where your graph is a path. If you remove $|S|$ vertices, then the connected components will be at most $|S| + 1$. You can think about how best to write that up; I suggest strong induction on the length of the path.
Once you establish the path case, you can address the general case. In general, your graph will contain a subgraph $P$ that is a path. From the path case, removing the vertices from $S$ and the edges other than the ones in $P$ will produce at most $|S| + 1$ components. Then you just need to justify why adding in extra edges will never increase the number of connected components (if a path exists between two vertices in the subgraph, then the same path will exist in the whole graph).