A bipartite graph with partite sets U and W is called balanced if |U| = |W|. Let G be a regular bipartite graph with at least one edge. Prove that G is balanced.

A regular graph means that every vertex has the same degree this implys that (using the bipartite property) the number of vertices in U = W again by it being bi partite and having vertices of equal degree implys that |U| = |W|.

At least in my head that makes sense any hint how to prove it?

  • 1
    $\begingroup$ A sketch of a proof: Suppose that $G$ is $d$-regular bipartite with bipartition $U,W$. For each $u\in U$ by the fact that the graph is $d$-regular there will be $d$ edges leaving $U$ with the other ends in $W$ since $G$ is bipartite. Each $u$ contributes $d$ such ends. Summing over all $u\in U$ this is $d|U|$ total ends with some unknown number of them overcounted. Each vertex in $W$ corresponds to exactly $d$ of those ends as well, again by regularity, leading us to knowing $|W|=(d|U|)/d$. This could be cleaned up, I'm sure, but it has some of the important observations. $\endgroup$
    – JMoravitz
    Sep 9 '17 at 0:41
  • $\begingroup$ The idea, for the record, being the "shepherd's principle," that to count the number of sheep in a field (containing only sheep and all sheep have four legs) you may instead count the number of legs and divide by four. $\endgroup$
    – JMoravitz
    Sep 9 '17 at 0:52
  • $\begingroup$ Thanks i figured it out now ^^ if you post the top as answer and ill accept. $\endgroup$
    – Faust
    Sep 9 '17 at 0:55

Let the degree of every node be $d$ (and since the graph has at least one edge, $d>0$). Then the number of edges associated with nodes in $U$ is $|U|d$, and the number of edges associated with nodes in $W$ is $|W|d$. Every edge in the bipartite graph connects a node in $U$ with a node in $W$, thus the total number of edges associated with the two parts is the same.

Thus $|U|d = |W|d$ and $|U| = |W|$

  • $\begingroup$ If $d>|U|/2$ then the graph must be connected. $\endgroup$
    – Joffan
    Sep 9 '17 at 3:57

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.