<p>Thanks to Tsuyoshi's comment, I have the solution.</p>

<p>It's always possible to take some subset of lefts (of size k) and construct a set of k bicliques covering all the edges connected to those lefts (assign each left to it's own biclique together with all its right-neighbors). This means that for any subset of k bicliques in the minimum biclique cover, there are at least k lefts contained in the union of those bicliques.</p>

<p>Now we can construct the bipartite graph which contains a left node for each biclique in the minimum cover and a right node for each left node in the original graph.  There is an edge between a left and right if the corresponding biclique contains the corresponding right in the original graph.  The lemma above translates exactly to the criteria for Hall's theorem in this new graph which means there exists a matching which saturates the left side.</p>

<p>This corresponds to an assignment of bicliques to lefts in the original graph.</p>

CC BY-SA 3.0
2014-11-19T03:17:50.477Z
2014-11-19T03:17:50.477Z
dspyz
<p>Given a minimum biclique edge cover, is it always possible to assign each biclique to a distinct left node (which it contains)?</p>

<p>ie one such assignment for this graph (from wikipedia): <a href="http://upload.wikimedia.org/wikipedia/commons/f/f7/Bipartite-dimension-biclique-cover.svg" rel="nofollow">http://upload.wikimedia.org/wikipedia/commons/f/f7/Bipartite-dimension-biclique-cover.svg</a> could be</p>

<p>(numbering the left vertices from 1 through 5 going down)</p>

<p>blue: 1</p>

<p>red: 2</p>

<p>green: 3</p>

<p>black: 4</p>

CC BY-SA 3.0
2014-11-18T19:15:00.730Z
Yes.  Hint: Hall’s theorem.
Tsuyoshi Ito
<graph-theory>
Assign each biclique to a distinct left
dspyz
# Assign each biclique to a distinct left

(Asked by: username_0 on 2014-11-18)

Given a minimum biclique edge cover, is it always possible to assign each biclique to a distinct left node (which it contains)?

ie one such assignment for this graph (from wikipedia): <http://upload.wikimedia.org/wikipedia/commons/f/f7/Bipartite-dimension-biclique-cover.svg> could be

(numbering the left vertices from 1 through 5 going down)

blue: 1

red: 2

green: 3

black: 4

**Tags:** graph-theory
> **Comments:**
> **username_1**: Yes.  Hint: Hall’s theorem.  

---

## 1 answers

### Answer by username_0 on 2014-11-19. Score: 0

Thanks to Tsuyoshi's comment, I have the solution.

It's always possible to take some subset of lefts (of size k) and construct a set of k bicliques covering all the edges connected to those lefts (assign each left to it's own biclique together with all its right-neighbors). This means that for any subset of k bicliques in the minimum biclique cover, there are at least k lefts contained in the union of those bicliques.

Now we can construct the bipartite graph which contains a left node for each biclique in the minimum cover and a right node for each left node in the original graph. There is an edge between a left and right if the corresponding biclique contains the corresponding right in the original graph. The lemma above translates exactly to the criteria for Hall's theorem in this new graph which means there exists a matching which saturates the left side.

This corresponds to an assignment of bicliques to lefts in the original graph.


---

