Gráfok 1.

1.

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

2.

Van-e olyan egyszerű gráf, amelyben a pontok foka rendre

(a)

1,2,2,3,3,3;

(b)

1,1,2,2,3,4,4;

(c)

5,5,5,6,6,6,7,7,7;

(d)

1,2,2,3,4,4,5,6,6;

(e)

1,1,3,3,3,3,5,6,8,9;

(f)

2,3,3,4,5,6,7?;

3.

Igazoljuk, hogy tetszőleges gráfban a páratlan fokú pontok száma páros.

4.

Hány olyan egyszerű gráf van, melynek fokszámai: 2,3,3,4,6,6,6?

5.

Milyen komponensekből állhat egy gráf, ha minden pontjának a foka legfeljebb 2?

6.

Jellemezzük azon gráfokat, melyekben minden kör páratlan hosszúságú.

7.

Hány 3 hosszú kör található abban a gráfban, amelyet az n szögpontú K_n teljes gráfból kapunk, ha egy élét elhagyjuk?

8.

Rajzoljuk fel az összes 3, 4, ill. 5 pontú fát (az izomorfakat csak egyszer).

9.

Hány olyan, páronként nem izomorf 5 pontú és 8 élű egyszerű gráf létezik, melyben pontosan két darab harmadfokú pont van?

10.

Hány páronként nem izomorf 4 pontú és 3 élű egyszerű irányított gráf létezik?

11.

Egy gráf izomorf a komplementerével. Mutassuk meg, hogy akkor összefüggő.

12.

Rajzoljunk a komplementerével izomorf 5, ill. 6 pontú gráfot.

13.

Keressünk olyan 8 pontú gráfot, hogy se ő, se a komplementere ne legyen síkbarajzolható.

14.

Egy negyedfokú reguláris összefüggő gráfból töröljük egy fa éleit. Bizonyítsuk be, hogy a maradék legalább két kört tartalmaz.

15.

Egy egyszerű páros gráfban minden pont foka legalább 4. Bizonyítsuk be, hogy van a gráfban olyan kör, melynek hossza legalább 8.

Vissza