MathDB
Bound of number of connected components

Source: St. Petersburg 2023 11.7

August 12, 2023
combinatorics

Problem Statement

Let GG be a connected graph and let X,YX, Y be two disjoint subsets of its vertices, such that there are no edges between them. Given that G/XG/X has mm connected components and G/YG/Y has nn connected components, what is the minimal number of connected components of the graph G/(X∪Y)G/(X \cup Y)?
Back to ProblemsView on AoPS