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!

  • $\begingroup$ I doubt that your algorithm works. Try to find a counterexample. $\endgroup$ Dec 5, 2017 at 21:42

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.