Decomposição em grafos bipartidos completos aresta-disjuntos

Decomposição de um grafo

Uma decomposição de um grafo \(G\) em grafos aresta-disjuntos consiste em encontrar subgrafos \(H_1,H_2,\ldots,H_k\) de \(G\) tais que cada aresta de \(G\) pertence a exatamente um deles. Em símbolos, temos

• \(\bigcup_{i=1}^k E(H_i)=E(G)\); e
• \(E(H_i)\cap E(H_j)=\emptyset\), para \(i\neq j\).

Decomposição em grafos bipartidos completos

Seja \(\tau(G)\) o número mínimo de subgrafos de \(G\) que são bipartidos completos, aresta-disjuntos, e que formam uma decomposição de \(G\).

A pergunta do dia é motivada pelo resumo (abstract) do artigo de Alon: mostre que\(|E(G)|\leq \tau(G)\leq |V(G)| - \alpha(G)\), onde \(\alpha(G)\) é o maior tamanho de um conjunto de vértices \(S\) tal que nenhuma aresta de \(G\) conecta vértices de \(S\).