Relembrando algumas definições
Grafo simples: não há duas arestas diferentes entre dois vértices e nenhuma aresta tem as suas extremidades no mesmo vértice.
Grafo $n$-regular: todos os vértices tem grau $n$.
Subgrafo gerador: $H$ é grafo gerador de $G$ se $V(H) = V(G)$.
$n$-fator: um subgrafo gerador $n$-regular.
Seria legal se fosse verdade
Imagina se para $k$ inteiro positivo existisse um $r$ suficientemente grande tal que todo grafo $r$-regular possui um subgrafo gerador $k$-regular. Seria legal, né? Será que conseguimos mostrar isso?
Não.
Motivação
Teorema de Petersen: Para todo $n$ inteiro positivo par, temos que todo grafo $n$-regular possui $\frac{n}{2}$ $2$-fatores sem arestas em comum.
Pelo Teorema de Petersen, conseguimos mostrar que para todo $r, k$ inteiros positivos pares tal que $r > k$, todo grafo $r$-regular tem um subgrafo gerador $k$-regular:
Como $r > k$, $\frac{r}{2} > \frac{k}{2}$, logo, se temos $\frac{n}{2}$ $2$-fatores, em particular temos $\frac{k}{2}$ $2$-fatores. Como esses $2$-fatores não tem arestas em comum, se unirmos $\frac{k}{2}$ deles teremos um subgrafo gerador $k$-regular!
Mas isso vale somente para $r, k$ pares, não conseguimos mostrar para o caso em que um dos dois (ou ambos) são ímpares.
Também conseguimos mostrar que para todo $k$ inteiro positivo e para todo $r$ inteiro positivo suficientemente grande, todo grafo $G$ $r$-regular contém um subgrafo $H$ $k$-regular.
Mas não conseguimos pedir que $H$ seja gerador.
A ideia
Dado um grafo $G$, diremos que um subgrafo $H$ é $\epsilon$-gerador se $V(H) \geq (1 - \epsilon)V(G)$. Diremos que $H$ é “quase gerador” se para todo $\epsilon > 0$ tivermos que $V(H) \geq (1 - \epsilon)V(G)$.
A ideia é mostrar que para todo $k$ inteiro positivo, existe um $r$ suficientemente grande tal que todo grafo $G$ $r$-regular contém um subgrafo $k$-regular “quase gerador”, ou seja, que contém quase todos os vértices de $G$.
Conjectura
Para todo $\epsilon > 0$ todo $k$ inteiro positivo existe $r_{0} = r_{0} (\epsilon, k)$ tal que todo grafo $G$ simples $r$-regular com $r \geq r_{0}$ tem um subgrafo $H$ $k$-regular com $|V(H)| \geq (1 - \epsilon)|V(G)|$.
O que já temos
O resultado foi provado para $k=1$ e $k=2$, mas permanece aberto para $k \geq 3$. Iremos demonstrar os casos $k = 1$ e $k = 2$, abordando algumas definições e teoremas necessários para essas demonstrações.
Coloração de arestas
Uma coloroção sobre as arestas é uma forma de colorir as arestas de um grafo de forma que duas arestas com mesma extremidade não tem mesma cor.
Teorema de Vizing
Para todo grafo simples não direcionado existe uma coloração de arestas com no máximo $\Delta + 1$ cores.
Note também que são necessárias pelo menos $\Delta$ cores.
Caso $k = 1$
Queremos mostrar que, para todo $\epsilon > 0$ existe $r_{0} = r_{0} (\epsilon)$ tal que todo grafo $G$ simples $r$-regular com $r \geq r_{0}$ tem um subgrafo $H$ $1$-regular com $|V(H)| \geq (1 - \epsilon)|V(G)|$.
Como o grafo $G$ é $r$-regular, $\Delta = r$. Logo, podemos particionar $G$ em $r + 1$ subgrafos (nos baseando na coloração das arestas). Vamos olhar para o maior desses subgrafos (com relação ao número de arestas). Primeiro, note que ele é $1$-regular: como duas arestas adjacentes não podem ter mesma coloração, quando consideramos o subgrafo apenas das arestas de uma certa cor, temos apenas arestas isoladas (ou seja, grafos $1$-regulares).
Já temos nosso subgrafo $1$-regular, falta mostrar que ele cobre quase todos os vértices.
A soma dos graus de todos os vértices de $G$ é $r|V(G)| = 2E(g)$. Temos então que $r|V(G)|/2 = E(G)$. Como dividimos essas arestas em $r + 1$ partições, a maior delas tem, pelo menos, $r|V(G)|/2(r+1)$ arestas, tendo, então, pelo menos $r|V(G)|/(r+1)$ vértices. Como $r/(r+1)$ tende a $1$ quando $r$ tende a infinito, para todo $\epsilon$ positivo existe um $r$ suficientemente grande tal que esse subgrafo cobre quase todos os vértice de $V(G)$.
Permanente
Dada uma matriz $n * n$, o permanente dessa matriz é $\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}$. Na prática, o permanente de uma matriz é seu determinante com todos os sinais positivos.
Essa ferramenta tem algumas aplicações em grafos. Em coberturas por ciclos, podemos olhar para uma matriz quadrada como a matriz de adjacências de um grafo direcionado com peso. Definindo o peso de uma cobertura por ciclos como o produto dos pesos dos arcos de cada ciclo, o permanente de $A$ é a soma dos pesos de todas as coberturas por ciclos do grafo. Algo semelhante pode ser feito com pareamentos perfeitos: uma matriz $n * n$ pode ser vista como um grafo bipartido com $n$ vértices de cada lado, onde cada entrada da matriz representa o peso da aresta correspondente. Definindo o peso do pareamento como o produto dos pesos de suas arestas, $perm(A)$ é a soma dos pesos de todos os pareamentos perfeitos dos grafos.
As conjecturas que utilizaremos
Conjectura de Minc: $perm(A) \leq \prod_{i=1}^{n} (r_{i}!)^{1/r_{i}}$, onde $r_{i}$ é a soma das entradas da $i$-ésima linha.
Conjectura de van der Waerden: dada uma matriz $n * n$ onde a soma de cada linha e cada coluna é $r$, o permanente desse matriz é, pelo menos, $(r/n)^{n}n!$. Além disso, se todas as entradas são inteiras, o permanente é pelo menos $((r-1)^{r-1}/r^{r-2})^{n}$.
Caso $k = 2$
Queremos mostrar que, para todo $\epsilon > 0$ \pause existe $r_{0} = r_{0} (\epsilon)$ \pause tal que todo grafo $G$ simples $r$-regular com $r \geq r_{0}$ \pause tem um subgrafo $H$ $2$-regular com $|V(H)| \geq (1 - \epsilon)|V(G)|$. Como é possível imaginar pelas conjecturas que utilizaremos, o caso $k = 2$ envolve algumas contas extensas, além de utilizar ferramentas que não são abordadas no curso e com as quais não estamos habituados. Por isso, não seria proveitoso estudá-la à fundo. Mas ela pode ser encontrada em Problems and results in Extremal Combinatorics, Part I - Noga Alon (páginas 4–5).
Curiosidades: mais algumas coisas nessa linha
Teorema: Para todo inteiro $g \geq 3$ e todo real $\epsilon > 0$ existe $r_{0} = (\epsilon, g)$ tal que para todo $r > r_{0}$ todo grafo $G$ $r$-regular contém um subgrafo $H$ $2$-regular tal que $|V(H)| \geq (1 - \epsilon)|V(G)|$ tal que o número de vértices em cada componente conexa de $H$ é maior ou igual a $g$.
Conjectura: Para todo grafo $H$ e todo real $\epsilon > 0$, existe $r_{0} = r_{0}(H, \epsilon)$ tal que, dado $r > r_{0}$, todo grafo $G$ $r$-regular tem um subgrafo com pelo menos $(1 - \epsilon)|V(G)|$ vértices que é uma coleção de grafos dois a dois vértice disjuntos tal que cada um desses grafos é uma cópia topológica de $H$.
Já foi mostrado para grafos acíclicos, para ciclos (pelo teorema anterior) e para grafos com somente um ciclo. Ainda está em aberto para grafos mais complicados.