MathDB
Edges in a Table

Source: Iran TST 2015, exam 1, day 2 problem 2

May 11, 2015
combinatoricsgraph theory

Problem Statement

Let AA be a subset of the edges of an n×nn\times n table. Let V(A)V(A) be the set of vertices from the table which are connected to at least on edge from AA and j(A)j(A) be the number of the connected components of graph GG which it's vertices are the set V(A)V(A) and it's edges are the set AA. Prove that for every natural number ll: l2≤min∣A∣≥l(∣V(A)∣−j(A))≤l2+l2+1\frac{l}{2}\leq min_{|A|\geq l}(|V(A)|-j(A)) \leq \frac{l}{2}+\sqrt{\frac{l}{2}}+1
Back to ProblemsView on AoPS