Skip to main content
MathOverflow

Return to Question

added 1 character in body; edited title
Source Link
Michael Hardy
Michael Hardy
  • 1
  • 12
  • 85
  • 126

Existence of adjacent $a, b$ in a general bipartite graph (with a special degree condition) such that $\frac{deg\deg(a)}{deg\deg(b)} \ge \frac{|B|}{|A|}$

Suppose a bipartite graph with two parts $A, B$, for every ${b \in B}$$b \in B$ we know $deg(b) \ge 1$$\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|}$$\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|}$

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|}$

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|}$.

Source Link
Nima Aryan
Nima Aryan
  • 149
  • 10

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|}$

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|}$.