Problem

Source: China Additional TST for IMO 2020, P6

Tags: combinatorics, graph theory



Given a simple, connected graph with $n$ vertices and $m$ edges. Prove that one can find at least $m$ ways separating the set of vertices into two parts, such that the induced subgraphs on both parts are connected.