Decide if there is a sbugroup of edges in graph that every vertex meets exactly k edges from subgroup

Question

I've been trying to solve the following question:

Show a polynomial algorithm for the following problem. Let $G = (V, > E)$ a graph. The goal is to decide if there is $E' ⊆ E$ , such that for every vertex $v ∈ V$, $v$ meets or exactly $k$ edges from $E'$. (Namely, for $k = 1$ you get the perfect matching problem). hint - start with $k = 2$, duplicate vertices.

I was able to develop an algorithm which works but I couldn't prove it find the largest subgroup, your help is needed :)

The algorithm:

For every $v$ in $V$:

1. Check the degree, if it equal to k or not connected to any edge in the subgroup - color it
2. Check if the colored $v$ has a colored vertex, if it has the edge between them belongs to the subgroup.
3. Traverse on all vertices (BFS or DFS) When done you'll find the subgroup, the only one thing the prove it is the largest and I couldn't find any proof for it.

Thanks in advance!

Answer 1

The question is a bit misleading, since the proposed algorithm finds whether there is a "multisubset" of the edges set which is $k$-regular — that is, you are allowed to take the same edge several times, if it helps. Deciding whether the graph contains a bona fide $k$-factor (a $k$-regular subgraph which touches all vertices) is much more tricky — see Meijer, Núñez-Rodríguez, and Rappaport, An algorithm for computing simple $k$-factors.