Rajzolható-e olyan ötpontú egyszerű gráf?

Igen, igen, nem, nem. Ha igen, azt ilyen kicsi gráfnál legegyszerűbb úgy belátni, hogy lerajzolsz egyet. Ha nem, akkor meg kell keresni egy ellentmondást, ami miatt lehetetlen. Pl a fokszámok összege nem páros (c) vagy van a pontok száma-1-nél nagyobb fokszám (d).

Nagyobb csúcsszám és fokszám esetén úgy érdemes eljárni, hogy a legnagyobb fokszámút összekötöd a többi legnagyobb fokszámúval, de csak annyival, amennyi a fokszáma, utána a soron következő legnagyobbal megcsinálod ezt, és ezt addig csinálod, míg nem lesz összekötve mindegyik csúcs a megfelelő számban a többivel, ha pedig nem rontod el, és mégsem jön ki, akkor nincs ilyen gráf. Ezt Hakimi-algoritmusnak hívják.

Ha a Hakimi algoritmus elakad akkor még nem lehet arra következtetni, hogy nincs olyan gráf!

Ha nem rontja el, akkor tudunk ellenpéldát mutatni, szóval következik belőle...

Ha a Hakimi nem fut le, az valóban ekvivalens azzal, hogy nincs olyan gráf, de nem azért, mert ellenpéldát adna. Nemlétezést nem lehet ellenpéldával bizonyítani.

Rosszul fogalmaztam; ehhez kapcsolódóan tartozik egy tétel, arra tudunk egy ellenpéldát mutatni, hogy létezik egy olyan csúcselosztás, amire túl sok él van.

Ennek fuss neki még egyszer, mert így nincs értelme.

Miért is nincs? ...

Mert nem derül ki belőle, mit akarsz mondani. Amit leírtál, az azt jelenti, hogy van egy tétel, és erre a tételre te tudsz ellenpéldát (tehát nem igaz).

Vagy ha másképp tagolod, akkor valaminek a létezésére tudsz ellenpéldát mutatni, ami még nagyobb hülyeség.