Separating vertices, retaining connectivity
Source: China Additional TST for IMO 2020, P6
October 19, 2020
combinatoricsgraph theory
Problem Statement
Given a simple, connected graph with vertices and edges. Prove that one can find at least ways separating the set of vertices into two parts, such that the induced subgraphs on both parts are connected.