Problem
COM-B2-M07-P015 Regular Bipartite Graph
#15
★★★★☆ Level 4 of 5
In a bipartite graph with parts \(A\) and \(B\), every vertex has degree \(d>0\). Prove that \(|A|=|B|\).
Count edges from the left part and from the right part.
Every edge has one endpoint in \(A\) and one endpoint in \(B\). Counting edges by vertices of \(A\), we get \(d|A|\). Counting by vertices of \(B\), we get \(d|B|\). These are the same number of edges, so \(d|A|=d|B|\). Since \(d>0\), we have \(|A|=|B|\).
A common double-counting lemma for bipartite graphs.