Byt färg i graf

Med en graf avses här en samling noder, eventuellt sammankopplade parvis med kanter. Vi utgår från en graf. Grafens noder kan färgmarkeras antingen vitt (V) eller svart (S). Från början är alla noder vita.

Man gör nu "drag" och förändrar färgmärkningen. Ett "drag" innebär att man väljer ur en nod och byter färg på denna och alla angränsande noder. Är det alltid möjligt att få alla noder svartmarkerade?

Ett enkelt exempel:

Men går det i vilken graf som helst?