Question

Care este numărul minim de muchii care trebuie eliminate dintr-un graf neorientat complet cu 100 de noduri astfel încât graful parţial obţinut să fie eulerian?

Stiu ca raspunsul e 50, dar de ce?

Answer 1

intr-un graf complet cu 100 de noduri, fiecare nod are gradul 99, iar ca sa fie graf eulerian, fiecare nod trebuie sa aibe grad par, astfel numarul minim de muchii pe care poti sa le elimini astfel incat fiecare nod sa aibe gradul 98 este 50 (pt ca iei cate o muchie de la fiecare nod, iar muchia se realizeaza intre 2 noduri asa ca inloc de 100 de muchii trebuie sa elimini 50)