- 1. feladat F M
(a) Hogyan találjuk meg
G
pontjait
L
(
G
)
-ben? (b) Valamely pontból három olyan
e
1
,
e
2
,
e
3
∈
E
(
G
1
)
él indul ki, hogy a megfelelő
e
1
′
,
e
2
′
,
e
3
′
∈
E
(
G
2
)
élek háromszöget alkotnak. (c)-re a
választ (b) megoldása tartalmazza.
- 2. feladat F M
(a) Mutassuk meg, hogy
|
E
∩
F
|
=
|
α
(
E
)
∩
α
(
F
)
|
bármely két
E
,
F
∈
E
(
K
n
r
)
esetén. (b) Mutassuk meg, hogy
„felismerhető”
L
(
K
n
r
)
-ben, ha két
r
-esnek
k
közös pontja van
k
=
r
−
1
-re; majd igazoljuk ezt
k
=
1
,
2
,
…
-re.
- 3. feladat F M
Ismét határozzuk meg
|
E
∩
F
|
-et
L
i
(
K
n
r
)
-ből a mind
E
-vel, mind
F
-fel szomszédos
r
-esek megszámolásával.
- 4. feladat F M
(a) Tekintsük a csillagok, kint az élek
részhalmazai által alkotott hipergráfot. (b) Amire
szükségünk van, az az élek lefedése
n
2
4
teljes részgráffal. Ezt a Turán
tételben (10.28) szereplő módszerhez hasonlóan tehetjük
meg.
- 5. feladat F M
(a) Használjuk fel 15.1b-t annak bizonyításához,
hogy a
H
x
gráfok „összeillenek”. (b) Az előző
feladatból nyilvánvaló.
- 6. feladat F M
(a) Ha
G
=
L
(
H
)
, akkor
H
éleinek azon hármasai, melyek
G
-ben páratlan háromszöget alkotnak,
egy csillaghoz tartoznak és viszont. (b) Definiáljuk
G
két
(
a
,
b
)
és
(
c
,
d
)
élét ekvivalensnek, ha azonosak, vagy
egy páratlan háromszögbe tartoznak, vagy egy teljes
négyszöget feszítenek. Mutassuk meg, hogy ez
ekvivalencia-reláció, az ekvivalencia-osztályok
15.4a-nak megfelelő az éleket lefedő teljes részgráfok,
és kevés eset kivételével egy kívánt
H
gráfot adnak, melyre
L
(
H
)
=
G
. (c) Hogyan lehet (a)-ban (ii)-t
megsérteni?
- 7. feladat F M
Igazoljuk, hogy a 20. ábrán látható gráf nem
élgráfja egyetlen többszörös élt nem tartalmazó
3-uniform hipergráfnak sem, viszont minden valódi
részgráfja az.
- 8. feladat F M
(a) Ez a következőt jelenti: keressük ugyanazon
síkbarajzolható gráfnak két lényegesen különböző
síkbaágyazását. (b) Használjuk 6.69-et.
- 9. feladat F M
(a) Tekintsünk két
(
x
,
y
)
,
(
x
,
z
)
élt és egy
y
-on és
z
-n áthaladó
G
1
−
x
-beli
C
kört. (b) 15.1b megoldása
egyszerűsített formában alkalmazható, hiszen ebben az
esetben nem lehet háromszögnek megfelelő
csillag.
- 10. feladat F M
Alkalmazzunk indukciót
r
-re, megmutatva azt, hogy
T
és
T
′
izomorfak (és
x
i
-nek
x
i
′
felel meg).
- 11. feladat F M
(a) Az előző megoldás egy azonosságából
következik. (b) hasonlóan adódik. (c) Konstruáljuk meg
T
-t indukcióval. Vegyünk két olyan
x
i
és
x
j
pontot, melyekre
minimális.
- 12. feladat F M
(a) Álljon
{
a
1
,
…
,
a
n
}
a
2
l
szám
k
+
1
2
l
példányából
0
≤
l
≤
k
+
1
2
-re,
{
b
1
,
…
,
b
n
}
pedig a
2
l
+
1
szám
k
+
1
2
l
+
1
példányából
0
≤
l
≤
k
2
-re. (b) Fejezzük ki a feltételt a
következő polinomok segítségével:
- 13. feladat F M
f
−
g
-t tekintve elég azt belátni, hogy
nem tűnhet el minden
s
1
,
…
,
s
k
≥
0
egészre, hacsak nem azonosan 0.
- 14. feladat F M
Először bizonyítsuk azt, hogy
G
1
és
G
2
élszáma azonos, majd azt, hogy
fokszámaik is azonosak.
- 15. feladat F M
(a) Tekintsünk két Hamilton kört
V
-n. (b) Számoljuk meg
H
-t minden
G
−
x
részgráfban. (c) Bizonyítsuk be, hogy
k
=
|
V
|
−
1
,
…
-re minden
k
pontú összefüggő gráf ugyanannyiszor
fordul elő
G
1
és
G
2
komponenseként.
- 16. feladat F M
(a)
T
i
átmérője a (
T
i
−
x
)-ek átmérői közül a maximális,
kivéve, ha
T
i
egy út. (b) Ha
T
i
−
x
átmérője minden
x
végpontra
d
, akkor
T
i
középpontra vonatkozó ágai a 15.9c-ben
alkalmazotthoz hasonló módszerrel konstruálhatók. Ha
egy
x
0
végpontot minden
d
hosszú út tartalmaz, akkor vizsgáljuk
meg, hogy minden
T
i
−
x
0
-beli
(
d
−
1
)
-hosszú út lefogható-e egyetlen
ponttal.
- 17. feladat F M
(a) Fejezzük ki a
G
1
G
2
-be és saját magába való
izomorfizmusainak számát az 5.18-ban szereplőhöz
hasonló formulával, és vegyük észre, hogy a jobb
oldalak azonosak. (b) Használjuk a szitaformula helyett
a 2.7b azonosságot.
- 18. feladat F M
Először mutassuk meg, hogy ha
(
∗
)
minden
k
elemű
X
-re fennáll, akkor fennáll minden
k
-nál kevesebb elemű
X
-re is (feltéve, hogy
k
≤
|
V
|
−
r
).
- 19. feladat F M
Tegyük fel, hogy
H
1
≠
H
2
. Mutassuk meg, hogy
∅
∈
E
(
H
1
)
vagy
∅
∈
E
(
H
2
)
; majd bizonyítsuk
k
szerinti indukcióval, hogy minden
k
méretű halmaz
k
paritásától függően vagy
H
1
-be, vagy
H
2
-be tartozik.
- 20. feladat F M
(a) Epimorfizmusra (
H
-ra való homomorfizmus) az állítás
triviális lenne. Fejezzük ki az epimorfizmusok számát a
homomorfizmusok számával. (b) „Dualizáljuk” (a)
megoldását.
- 21. feladat F M
Mutassuk meg, hogy
H
G
×
G
-be való homomorfizmusainak száma
négyzete a
H
G
-be való homomorfizmusai
számának.
- 22. feladat F M
(a) Próbálkozzunk
F
=
K
2
-val; vegyük észre, hogy
G
1
és
G
2
fokszám-sorozata azonos kell, hogy
legyen. (b) Érveljünk az előző feladathoz hasonlóan.
(c) Legyen
G
∘
a
G
-ből minden pontnál egy hurokél
felvételével előálló gráf. Ekkor
(
G
⋅
H
)
∘
=
G
∘
×
H
∘
. (d) A fentiekhez hasonlóan, ha két
csoport rendelkezik azzal a tulajdonsággal, hogy minden
csoportnak mindkettőbe ugyanannyi homomorfizmusa van,
akkor izomorfak.