MathDB
BMT 2014 Spring - Discrete P2

Source:

January 6, 2022
combinatoricsgraph theory

Problem Statement

Given an integer n≥2n\ge2, the graph GG is defined by:
- Vertices of GG are represented by binary strings of length nn - Two vertices a,ba,b are connected by an edge if and only if they differ in exactly 22 places
Let SS be a subset of the vertices of GG, and let S′S' be the set of edges between vertices in SS and vertices not in SS. Show that if ∣S∣|S| (the size of SS) ≤2n−2\le2^{n-2}, then ∣S′∣≥∣S∣|S'|\ge|S|.
Back to ProblemsView on AoPS