Egy egyszerű gráfnak 10 éle van. Adja meg a csúcsok számának legkisebb és legnagyobb lehetséges értékét?

legnagyobb: egyszerű gráfban n-1 az élek maximális száma (önmagán kívül minden ponttal összekötünk egy pontot és mást nem), így 11 a csúcsok számának legnagyobb értéke

legkisebb: a teljes gráfban minden pont össze van kötve a többivel, így ebben az esetben lesz a legkevesebb csúcs. az n csúcsú teljes gráfban az élek száma

n(n-1)/2, tehát most 10=n*(n-1)/2, vagyis 0=n^2-n-20 n=5(negatív ugye nem lehet így a -4 nem jó)

Az, hogy egy gráf egyszerű, azt jelenti, hogy nincsenek se hurokélei, se többszörös élei, tehát maximum (pontok száma alatt a 2) db éle van. Ezért minimum 5 pontra van szükség.

Maximuma nincs a pontok lehetséges számának. Ha veszel egy ötpontú teljes gráfot, és hozzá akárhány 0 fokszámú pontot, akkor mindig egy olyan egyszerű gráfot kapsz, aminek 10 éle van.

Amire a többi válaszoló gondol, az az ÖSSZEFÜGGŐ gráf lenne.