Raspunsul corect: a) 3
Graf eulerian = graf in care putem traversa intr-un ciclu toate muchiile fara a traversa de doua ori aceasi muchie.
Teorema: Un graf neorientat fără vârfuri izolate este eulerian dacă și numai dacă este conex și toate vârfurile au grad par.
Vedem ca graful e conex, conditie indeplinita.
Nodurile 3 si 4 au grad impar.
Nu putem sa le legam intre ele pentru ca sunt legate deja, motiv pentru care va trebui sa legam 3 de inca un nod din partea dreapta (6 de exemplu) si 4 de un nod din partea stanga (1 de exemplu), ceea ce inseamna 2 muchi (am marcat cu mov). Dar acum nodurile de care am legat au grad impar (1 si 5 au grad impar) si vom folosi inca o muchie sa le legam intre ele, ambele avand astfel acum grad par.
Deci trebuie sa folosim inca 3 muchii cel putin
