Van-e olyan (legalább kétpontú) gráf, melyben minden pont foka különböző?

Nyilván egyszerű gráfra gondolsz, mert nem egyszerű van ilyen: kétpontú gráf, ahol az egyik izolált pont, a másikon meg van egy hurokél.

Egyszerű gráfok esetén azonban, ha n db csúcs van, a legnagyobb fokszámú csúcs fokszáma csak n-1 lehet, hiszen sem hurokélek, sem többszörös élek nem lehetnek, és csak n-1 másik csúccsal lehet összekötve. Vagyis a legkisebb fokszám emiatt csak 0 lehet (0, 1, 2,..., n-1), ezzel azonban ellentmondunk annak, hogy a legnagyobb fokszámú csúcs mindegyik másikkal össze van kötve.

Ergo ilyen gráf nem létezik.