Do que por mim passa... - Grafos e Aplicações

Teorema do Casamento

Versão formal: Se G é um grafo bipartido, regular de ordem k, então G admite um emparelhamento perfeito.

Versão informal: Se cada rapariga de uma aldeia conhece exactamente k rapazes e cada rapaz da aldeia conhece exactamente k raparigas então cada rapariga pode casar com um rapaz que conhece e cada rapaz pode casar com uma rapariga que ele conhece.