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 :)
For every $v$ in $V$:
- Check the degree, if it equal to k or not connected to any edge in the subgroup - color it
- Check if the colored $v$ has a colored vertex, if it has the edge between them belongs to the subgroup.
- 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!