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|}$.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Is this homework? $\endgroup$– Brendan McKayCommented Dec 9, 2023 at 12:31
-
$\begingroup$ @BrendanMcKay No this is just a problem from one of my exams and I just try to upsolve it. $\endgroup$– Nima AryanCommented Dec 10, 2023 at 17:04
-
$\begingroup$ Maybe a pigeonhole type of argument? $\endgroup$– Michael HardyCommented Dec 11, 2023 at 18:20
-
$\begingroup$ This is well known when $|A|=|B|$, and the same trick works for your problem $\endgroup$– Fedor PetrovCommented Dec 11, 2023 at 19:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Let each vertex $b\in B$ have a can of jam of weight 1, and share it with all neighbours from $A$ equally. There should be a vertex $a\in A$ which got at least $|B|/|A|$ of jam, she got at least $|B|/(\deg(a) \cdot |A|)$ of jam from certain vertex $b$. This pair works.
answered Dec 11, 2023 at 19:37
-
1$\begingroup$ When I mention this version of double counting, I'm often met with disbelief. There are generalizations to more than two sets. $\endgroup$ Commented Dec 12, 2023 at 3:09