Whenever you visit a node you need one edge to walk in and one to walk out, except for the first and last node. So all K_n with even n , you can walk all the edges. For odd n, you lose one edge per node, except for 2 of them