Suppose a bipartite graph with two parts $A, B$, for every ${b \in B}$ we know $deg(b) \ge 1$.
Prove there exists an adjacent $a \in A, b \in B$ such that $\frac{deg(a)}{deg(b)} \ge \frac{|B|}{|A|}$.
Existence of adjacent $a, b$ in a general bipartite graph (with a special degree condition) such that $\frac{deg(a)}{deg(b)} \ge \frac{|B|}{|A|}$
Nima Aryan
- 149
- 10