===== Bipartite graph =====
==== Set ====
| @#55CCEE: context     | @#55CCEE: $V$ ... set |
| @#FFBB00: definiendum | @#FFBB00: $\langle V,E\rangle \in \mathrm{it}(E,V) $ |
| @#55EE55: postulate   | @#55EE55: $ \langle V,E\rangle $ ... undirected graph |
| @#DDDDDD: range       | @#DDDDDD: $ X\cup Y=V $ |
| @#DDDDDD: range       | @#DDDDDD: $ X\cap Y=\emptyset $ |
| @#DDDDDD: range       | @#DDDDDD: $ v,w\in V $ |
| @#55EE55: postulate   | @#55EE55: $\exists X,Y.\ \forall u,v.\ \{u,v\}\in E\implies \neg(u\in X\land v\in X)\land \neg(v\in Y\land u\in Y) $ |

==== Discussion ====
We denote the graph $G$ with bipartition $X,Y$ by $G[X,Y]$ and call $X$ and $Y$ its parts.
=== Theorems ===
A bipartite graph $G[X,Y]$ has $n=|X|+|Y|$ vertices and so has at most $|X|\cdot|Y|=|X|\cdot(n-|X|)$ edges. With respect to maximizing edge number, the optimal situation is $|X|=|Y|=n/2$ where $n^2/4$ can be reached.

If the graph is also $k$-regular with $k\ge 1$, then automatically $|X|=|Y|$.

Since for each edge, one end lies in $X$ and one in $Y$, we have $\sum_{v\in X}d(v)=\sum_{v\in Y}d(v)$
==== Parents ====
=== Refinement of ===
[[k-partite graph]]