Bipartite graph

Set

context $V$ … set
definiendum $\langle V,E\rangle \in \mathrm{it}(E,V) $
postulate $ \langle V,E\rangle $ … undirected graph
range $ X\cup Y=V $
range $ X\cap Y=\emptyset $
range $ v,w\in V $
postulate $\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

Link to graph
Log In
Improvements of the human condition