O Teorema de Erdős-Pósa
Grande parte do encanto dos teoremas de Konig e Hall na reside no fato de que eles garantem a existência do emparelhamento desejado assim que alguma obstrução óbvia não ocorra. No teorema de Konig, podemos encontrar $k$ arestas independentes em nosso grafo, a menos que possamos cobrir todas as suas arestas com menos de $k$ vértices (caso em que é obviamente impossível).
De forma mais geral, se $G$ é um grafo arbitrário, não necessariamente bipartido, e $\mathcal{H}$ é qualquer classe de grafos, podemos comparar o maior número $k$ de grafos de $\mathcal{H}$ (não necessariamente distintos) que podemos agrupar separadamente em $G$ com o menor número $s$ de vértices de $G$ que cobrirá todos os seus subgrafos em $\mathcal{H}$. Se $s$ pode ser limitado por uma função de $k$, ou seja, independentemente de $G$, dizemos que $\mathcal{H}$ tem a propriedade Erdős-Pósa. Assim, formalmente, $\mathcal{H}$ tem esta propriedade se existe uma função $\mathbb{N} \to \mathbb{N}$ $k \mapsto f(k)$ tal que, para todo $k$ e $G$, ou $G$ contém $k$ subgrafos disjuntos, cada um isomórfico a um grafo em $\mathcal{H}$, ou existe um conjunto $U \subseteq V(G)$ de no máximo $f(x)$ vértices tal que $G-U$ não tem subgrafo em $\mathcal{H}$.
Nosso objetivo aqui é provar o Teorema de Erdős e Pósa de que a classe de todos os ciclos possui esta propriedade: devemos encontrar uma função $f$ (cerca de $4k \log k$) tal que todo grafo contenha $k$ ciclos disjuntos ou um conjunto de no máximo $f(k)$ vértices cobrindo todos os seus ciclos.
Começamos provando uma afirmação mais forte para grafos cúbicos. Para $k \in \mathbb{N}$, coloque
$$s_{k} := \begin{cases} 4kr_{k}, & \mbox{se } k \geq 2\\ 1, & \mbox{se} k \leq 1 \end{cases}$$
onde $r_{k} := \log (k) + \log \log k+4$.
Lema
Seja $k \in \mathbb{N}$, e seja $H$ um multigrafo cúbico. Se $|H| \geq s_{k}$, então $H$ contém $k$ ciclos disjuntos.
Demonstração:
Aplicamos indução em $k$. Para $ \leq 1$ a afirmação é trivial, então seja dado $k \geq 2$ para a etapa de indução. Seja $C$ o ciclo mais curto em $H$.
Primeiro mostramos que $H-C$ contém uma subdivisão de um multigrafo cúbico $H'$ com $|H'| \geq |H|-2|C|$. Seja $m$ o número de arestas entre $C$ e $H-C$. Como $H$ é cúbico e $d(C) = 2$, temos $m \leq |C|$. Agora consideramos as bipartições $\{V_1,V_2\}$ de $V(H)$, começando com $V_1 := V(C)$ e permitindo $V_2 = \emptyset$. Se $H[V_2]$ tem um vértice de grau no máximo $1$ movemos este vértice para $V_1$, obtendo uma nova partição $\{V_1, V_2\}$ atravessada por menos arestas. Suponha que possamos realizar uma sequência de $n$ tais movimentos, mas não mais. (Nossas suposições implicam $n \leq 3$, mas não precisamos disso formalmente.) Então a partição resultante $\{V_1,V_2\}$ é atravessada por no máximo $m-n$ arestas. E $H[V_2]$ tem no máximo $m-n$ vértices de grau menor que $3$, pois cada um deles é incidente com uma aresta de cruzamento. Esses vértices têm grau exatamente $2$ em $H[V_2]$, pois não poderíamos movê-los para $V_1$. Seja $H'$ o multigrafo cúbico obtido de $H[V_2]$ suprimindo esses vértices. Então
$$|H'| \geq |H|-|C|-n-(m-n) \geq |H| -2|C|$$
como desejado.
Para completar a prova, basta mostrar que $|H'| \geq s_{k-1}$. Sendo $|C| \leq 2 \log |H|$ pelo Corolário (ou por $|H| \geq s_{k}$, se $|C|=g(H) \leq 2$), e $|H| \geq s_{k} \geq 6$, temos
$$|H'| \geq |H|-2|C| \geq |H| -4 \log |H| \geq s_{k}-4 \log s_{k}.$$
(Na última desigualdade usamos que a função $x \mapsto x-4 \log x$ aumenta para $x \geq 6$.)
Resta mostrar que $s_{k} -4 \log s_{k} \geq s_{k-1}$. Para $k=2$ isso é claro, então assumimos que $k \geq 3$. Então $r_{k} \leq 4 \log k$ (que é óbvio para $k \geq 4$, enquanto o caso de $k=3$ deve ser calculado) e, portanto,
$$s_{k} -4 \log s_{k} = 4(k-1)r_{k} +4 \log k + 4 \log \log k +16 -(8+4 \log k -4 \log r_{k})$$ $$\Downarrow$$ $$ s_{k} -4 \log s_{k} \geq s_{k-1} +4 \log \log k +8 -4 \log (4 \log k) = s_{k-1}$$ $$\Downarrow$$ $$ s_{k} -4 \log s_{k} \geq s_{k-1}$$
Como desejado.
Teorema de Erdős & Pósa (1965)
Existe uma função $f : \mathbb{N} \to \mathbb{N}$ tal que, dado qualquer $k \in \mathbb{N}$, todo grafo contém $k$ ciclos disjuntos ou um conjunto de no máximo $f(k)$ vértices que atendem a todos os seus ciclos.
Demonstração:
Mostramos o resultado para $f(k) := \lfloor s_{k} +k -1 \rfloor$. Seja $k$ dado e seja $G$ qualquer grafo. Podemos supor que $G$ contém um ciclo e, portanto, tem um subgrafo máximo $H$ no qual todo vértice tem grau $2$ ou $3$. Seja $U$ seu conjunto de vértices de grau $3$.
Seja $\mathcal{C}$ o conjunto de todos os ciclos em $G$ que evitam $U$ e encontram $H$ em exatamente um vértice. Seja $Z \subseteq V(H) \setminus U$ o conjunto desses vértices. Para cada $z \in Z$ escolha um ciclo $C_{z} \in \mathcal{C}$ que encontre $H$ em $z$, e coloque $\mathcal{C}' := \{C_{z} \mid z \in Z\}$. Pela maximalidade de $H$, os ciclos em $\mathcal{C}'$ são disjuntos.
Seja $\mathcal{D}$ o conjunto das componentes $2$-regulares de $H$ que evitam $Z$. Então $\mathcal{C}' \cup \mathcal{D}$ é outro conjunto de ciclos disjuntos. Se $|\mathcal{C}' \cup \mathcal{D}| \geq k$ , terminamos. Caso contrário, podemos adicionar a $Z$ um vértice de cada ciclo em $\mathcal{D}$ para obter um conjunto $X$ de no máximo $k-1$ vértices que atende a todos os ciclos em $\mathcal{C}$ e todos os componentes $2$-regulares de $H$. Agora considere qualquer ciclo de $G$ que evite $X$. Pela maximalidade de $H$ ele encontra $H$. Mas não é um componente de $H$, não está em $\mathcal{C}$ e não contém um $H$-caminho entre vértices distintos fora de $U$ (pela maximalidade de $H$). Portanto, este ciclo encontra $U$.
Mostramos que todo ciclo em $G$ encontra $X \cup U$. Como $|X| \leq k-1$, basta mostrar que $|U| < s_{k}$, a menos que $H$ contenha $k$ ciclos disjuntos. Mas isso decorre do Lema acima aplicado ao multigrafo obtido de $H$ suprimindo seus vrtices de grau $2$.
Referências
- Reinhard Diestel. “Graph Theory” .5th Electronic Edition 2016, pp. 45-47. Acesso em 15/05/2023.