6

Part of 2020 China Team Selection Test

Problems(1)

Separating vertices, retaining connectivity

Source: China Additional TST for IMO 2020, P6

Given a simple, connected graph with

n

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.

combinatoricsgraph theory