![](/files/happy5.png)
![$ \epsilon > 0 $](/files/tex/9347bd4719a266c10e0c73946c70533f2b4266a2.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ r_0 = r_0(\epsilon,k) $](/files/tex/db5402d669245c54e19a91ddcff575973e28c243.png)
![$ r $](/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ r \ge r_0 $](/files/tex/a0a00ac7aea9a9f3036fbe5546201edb3c16e8fa.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ |V(H)| \ge (1- \epsilon) |V(G)| $](/files/tex/d1aa8f81bdb2c1c340902bd11eadc4173d757e30.png)
Petersen's theorem asserts that every regular graph of even degree contains a 2-factor (i.e. a spanning 2-regular subgraph). Iterating this easy result we find that for any pair of positive even integers , every
-regular graph has a spanning
-regular subgraph. The cases when either
or
is odd are considerably more complicated. There are some nice general results (see [AFK]) which show that every regular graph of sufficiently high degree contains a
-regular subgraph. However these theorems give no bound on the size of this subgraph.
For this conjecture is an easy consequence of Vizing's Theorem. Indeed, this theorem implies that every
-regular graph
has a 1-regular subgraph
with
(just choose a largest color class from a
-edge coloring). Alon [A] proved the conjecture for
with the help of two famous results on permanents: the Minc Conjecture (proved by Bregman), and the van der Waerden conjecture (proved by Falikman and Egorichev). It is open for all
.
Bibliography
*[A] N. Alon, Problems and results in extremal combinatorics, J, Discrete Math. 273 (2003), 31-53.
[AFK] N. Alon, S. Friedland and G. Kalai, Regular subgraphs of almost regular graphs, J. Combinatorial Theory, Ser. B 37(1984), 79-91.
* indicates original appearance(s) of problem.