1
$\begingroup$

Let $G$ be a bipartite graph $G(V,E)$ with vertices partitioned into sets $V_1$ and $V_2$ such every vertex in $V_1$ has the same degree and every vertex in $V_2$ has the same degree.

How do I prove that the $\frac{\deg V_1}{\deg V_2}$ = $\frac{|V_2|}{|V_1|}$?

$\endgroup$
1
$\begingroup$

You should count the number of edges in two different ways. Assume the vertices in $V_1$ have degree $a$ and the vertices in $V_2$ have degree $b$. Then if we count the edges leaving $V_1$, well there are $a$ edges leaving each vertex, so there are $a\cdot |V_1|$ edges all together. Similarly if we count the edges by seeing how many leave $V_2$, we get that there are $b\cdot |V_2|$ edges. Thus $$a\cdot |V_1|=b\cdot |V_2|.$$ Thus we get the desired result.

$\endgroup$
  • $\begingroup$ I'm sorry I don't completely understand why can we set this equal to each other? $\endgroup$ – Tyler Dec 14 '16 at 17:27
  • $\begingroup$ wait nevermind, got it thank you! $\endgroup$ – Tyler Dec 14 '16 at 17:30
  • $\begingroup$ You set them equal to each other because they are both counting the same thing. This could be considered a very basic combinatorial proof(a proof of an equation by showing both sides count the same thing.) If you feel my answer has adequate addressed your question, feel free to accept it in order to close the question. $\endgroup$ – Sean English Dec 14 '16 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.