===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.