- 1. feladat F M
A Petersen gráf a
K
5
élgráfjának komplementere.
- 2. feladat F M
(a) Tekintsük a 16. ábrán mutatott típusú
kockákat. (b) A kocka esetére tekintsük a 4
főátlót.
- 3. feladat F M
Egy
k
hosszúságú kör tartalmaz néhány
fölösleges automorfizmust; hogy előzhetjük meg, hogy
irányt változtasson?
- 4. feladat F M
Tetszőleges fix elemmel jobbról szorozva a
G
egy automorfizmusát kapjuk.
- 5. feladat F M
Hagyjuk el az irányításokat és a színezéseket a
12.3-beli módszerhez hasonlóan.
- 6. feladat F M
Legyen
{
h
1
,
…
,
h
m
}
a
Γ
generátorainak egy minimális halmaza.
Vegyük a
Γ
×
{
1
,
2
}
elemeit, mint pontokat, és akkor és
csak akkor kössük össze
(
g
,
1
)
-et
(
g
′
,
2
)
-vel, ha
g
′
g
−
1
=
h
i
teljesül valamilyen
i
-re. Adjunk még hozzá éleket a
Γ
×
{
1
}
és
Γ
×
{
2
}
-n belül, annak biztosítására, hogy ne
kapjunk más automorfizmust, mint amelyeket a
Γ
elemei indukálnak természetes
módon.
- 7. feladat F M
(a) Egy páros rendű csoportnak van másodrendű
eleme. (b) Keressük meg az összes olyan turnamentet,
melyeknek automorfimuscsoportja tartalmaz egy
Γ
-val izomorf reguláris
részcsoportot.
- 8. feladat F M
Ugyanazzal a fajta konstrukcióval próbálkozva,
mint 12.5-ben, könnyű megkapni minden, nem
V
(
G
0
)
-beli pontot úgy, hogy 3 legyen a
foka. Ezután hasítsuk szét
G
0
minden pontját elsőfokú pontokra és
kössük össze őket egy körrel.
- 9. feladat F M
Legyen
x
1
,
x
2
,
…
,
x
n
a
G
pontjainak egy olyan elrendezése, hogy
i
>
1
esetén
x
i
össze van kötve
x
j
-vel, ahol
j
<
i
. Tekintsük az automorfizmusok egy
olyan részcsoportját, melyek fixen hagyják
x
1
,
…
,
x
i
-t.
- 10. feladat F M
Elegendő tekinteni az
A
(
G
)
egy pályáját az
E
(
G
)
-n.
- 11. feladat F M
Először oldjuk meg a
Γ
2
=
{
1
}
esetet. Ezután tekintsük példáknak egy
bizonyos „szorzatát”.
- 12. feladat F M
(a) Tekintsünk egy maximális
T
fát, melyre
T
∩
γ
(
T
)
=
∅
teljesül minden
γ
∈
Γ
,
γ
≠
1
esetén, és húzzuk össze mindegyik
γ
(
T
)
-t. (b) Legyen
e
∈
E
(
R
)
, legyen
G
1
az a részgráf, melyet az
e
Γ
által létrehozott képei alkotnak, és
próbáljuk meg összehúzni a
G
1
komponenseit.
- 13. feladat F M
(a) Egy kommutatív és tranzitív permutációcsoport
reguláris. Rögzítsünk egy
x
0
∈
V
(
G
)
csúcspontot, és tekintsünk egy
α
(
x
0
)
↦
α
−
1
(
x
0
)
(
α
∈
A
(
G
)
). (b) Az
n
-dimenziós kocka majdnem jó
lesz.
(c) Tekintsük az
n
-dimenziós
Q
n
kockát és egy
x
csúcspontját. Adjunk hozzá néhány az
x
szomszédai közötti élt, és mindazokat
az éleket, amelyeket a
Q
n
automorfizmusai kényszerítenek ki,
melyek megőrzik az élek irányát. Mi lesz az
x
szomszédai által feszített
részgráf?
- 14. feladat F M
Használjunk a 6.49. megoldásához hasonló
gondolatmenetet.
- 15. feladat F M
(a)–(b) Tekintsünk egy minimális
X
halmazt, mely a
G
−
T
komponense, valamely minimális
T
elvágóhalmazra. Használjuk 6.60(a)-t.
Az összefüggőség legalább
2
3
(
r
+
1
)
.
(c) Használjuk ismét 6.60(a)-t.
- 16. feladat F M
Használjuk a Tutte tételt, 7.27-et és
12.14-et.
- 17. feladat F M
Egy kör és egy út direkt szorzata tartalmaz egy
Hamilton kört.
- 18. feladat F M
Az összefüggőek a következők: a körök; a
szabályos testek; a kocka és a dodekaéder élgráfja;
gráfok, melyeket úgy nyerünk, hogy minden élt
ugyanazzal a számmal szorzunk meg; ezen példák
élfelbontásai úgy, hogy minden élre teszünk még egy
pontot; a kocka és a dodekaéder élgráfjának duálisa; és
a csillagok.
- 19. feladat F M
Használjuk 12.12(b)-t és az előző
megoldást.
- 20. feladat F M
(a) Mutassuk meg, hogy két
p
−
1
hosszúságú út és egy
K
2
direktszorzata összehúzható
K
p
-re.
(b) Feltehetjük, hogy
Γ
′
él-tranzitíven hat, és
Γ
nem hat félig regulárisan. Használjuk
10.8-at.
(c) Tekintsünk egy egyszerű csoportot.
- 21. feladat F M
Konstruáljunk egy egyszerű
G
gráfot, melyre
A
(
G
)
≅
Γ
és kössük össze
Ω
pontjaival alkalmas módon.
- 22. feladat F M
A Petersen gráf minden endomorfizmusa
automorfizmus.
- 23. feladat F M
Használjuk ugyanazt az ötletet, mint az előző
megoldásban: minden endomorfizmus kölcsönösen
egyértelmű egy minimális páratlan körön.
- 24. feladat F M
(a) Ugyanúgy megy, mint 12.4. (b) Amikor
színezett éleket utakkal helyettesítünk, melyekhez
hozzáragasztottunk darabokat, használjunk sok merev
gráfot, melyeknek nincs homomorfizmusuk
egymásba.
- 25. feladat F M
(a) Vagy 0, vagy
−
1
endomorfizmus marad. (b) Módosítsuk az
előző konstrukciót.