Bipartite graph
Set
| context | V … set |
| definiendum | ⟨V,E⟩∈it(E,V) |
| postulate | ⟨V,E⟩ … undirected graph |
| range | X∪Y=V |
| range | X∩Y=∅ |
| range | v,w∈V |
| postulate | ∃X,Y. ∀u,v. {u,v}∈E⟹¬(u∈X∧v∈X)∧¬(v∈Y∧u∈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|⋅|Y|=|X|⋅(n−|X|) edges. With respect to maximizing edge number, the optimal situation is |X|=|Y|=n/2 where n2/4 can be reached.
If the graph is also k-regular with k≥1, then automatically |X|=|Y|.
Since for each edge, one end lies in X and one in Y, we have ∑v∈Xd(v)=∑v∈Yd(v)
Parents
Refinement of
