- 1. feladat F Ö
(a) Legyenek
e
1
,
…
,
e
k
k
≥
4
egy adott
x
∈
V
G
ponthoz illeszkedő élek. Ekkor
e
1
,
…
,
e
k
L
G
egy teljes részgráfját alkotják.
Továbbá
L
G
-nek maximális teljes részgráfját
(klikkjét) alkotják; hiszen ha
e
∈
E
G
bármely más él, akkor nem tartalmazza
x
-et, így
e
1
,
…
,
e
k
közül legfeljebb kettővel
szomszédos.
Megfordítva, legyen
e
1
,
…
,
e
k
L
G
egy klikkje,
k
≥
4
, ekkor azt állítjuk hogy ezek
G
egy bizonyos pontjához illeszkedő
élek. Hiszen legyen
x
az
e
1
és
e
2
közös pontja. Ha
e
3
,
…
,
e
k
szintén tartalmazza
x
-et, akkor készen vagyunk, mivel a
G
e
1
,
…
,
e
k
élei által alkotott teljes részgráf
maximalitása miatt nincs más él, mely tartalmazhatná
x
-et.
Indirekte tegyük fel, hogy
e
3
nem tartalmazza
x
-et, ekkor
e
1
,
e
2
és
e
3
háromszöget alkot. Mivel
k
≥
4
, van
e
4
is; nyilvánvaló, hogy
e
4
nem csatlakozhat
e
1
,
e
2
és
e
3
mindegyikéhez, ami
ellentmondás.
A fenti állítások azt mutatják, hogy ha
G
-ben minden pont foka legalább 4,
akkor
G
előáll
L
G
-ből a következőképpen: Legyenek
C
1
,
…
,
C
n
az
L
G
azon klikkjei (maximális teljes
részgráfjai), melyek legalább 4 pontot tartalmaznak;
rendeljünk egy
x
i
pontot minden
C
i
-hez és akkor és csak akkor kössük
össze
x
i
-t és
x
j
-t, ha
C
i
-nek és
C
j
-nek van közös pontja. Az így előálló
G
′
gráf
G
-vel izomorf lesz.
Tehát ha
G
1
és
G
2
olyan gráfok, melyekben minden pont
foka legalább 4 és
L
G
1
≅
L
G
2
, akkor
G
1
-et és
G
2
-t a fentiek szerint „rekonstruálva”
izomorf gráfokat kapunk.
(b) Legyenek
S
1
,
…
,
S
n
a
G
1
pontjainak csillagai és legyenek
S
1
′
,
…
,
S
m
′
a
G
2
pontjainak csillagai. Tekintsünk egy
σ
:
L
G
1
→
L
G
2
izomorfizmust. Feltehetjük, hogy
n
≥
m
.
σ
S
i
nem lehet csillag minden
i
=
1
,
…
,
n
-re. Hiszen ha
σ
S
i
csillag, akkor
σ
S
i
,
σ
S
j
i
≠
j
különböző csillagok (mivel
S
i
≠
S
j
, a
G
1
≅
K
2
triviális eset kivételével, ami
figyelmen kívül hagyunk) és így az következne, hogy
m
=
n
,
σ
S
i
=
S
i
′
i
=
1
,
…
,
n
az indexek megfelelő választásával. De
ekkor
S
i
középpontját leképezve
S
i
′
i
=
1
,
…
,
n
középpontjába
G
1
és
G
2
közti izomorfizmust kapunk.
Tehát (mondjuk)
σ
S
1
nem csillag. Azt állítjuk, hogy van
három
e
1
,
e
2
és
e
3
él
G
1
-ben, melyek az
e
1
′
,
e
2
′
és
e
3
′
G
2
-beli éleknek felelnek meg és egyik
gráfban háromszöget alkotnak, a másikban
csillagot.
1
∘
Ha
S
1
=
1
, vagyis
S
1
=
{
e
1
}
, akkor
e
1
′
=
ϱ
e
1
egyik végpontja sem lehet elsőfokú.
Így tehát van két
e
2
′
,
e
3
′
≠
e
1
′
él, melyek
e
1
′
két végpontjából indulnak.
e
2
=
σ
−
1
e
1
′
és
e
3
=
σ
−
1
e
3
′
szomszédos
e
1
-gyel, ami csak akkor lehetséges, ha
e
1
azonos végpontjából indulnak. De ekkor
e
2
′
és
e
3
′
is szomszédos lesz, azaz
e
1
′
,
e
2
′
és
e
3
′
háromszöget alkot.
2
∘
Ha
S
1
=
{
e
1
,
e
2
}
, akkor
e
1
′
=
σ
e
1
-nek és
e
2
′
=
σ
e
2
-nek van egy közös
x
′
pontja. Kell lennie egy további
x
′
-ből induló
e
3
′
élnek.
e
3
=
σ
−
1
e
3
′
mind
e
1
-gyel, mind
e
2
-vel szomszédos, tehát háromszöget
alkotnak.
3
∘
Ha
S
1
=
{
e
1
,
e
2
,
e
3
}
, akkor
e
1
′
,
e
2
′
és
e
3
′
háromszöget kell, hogy alkosson;
ellenkező esetben ugyanabból a pontból indulnának, és
mivel
σ
S
i
nem csillag, lenne egy mindhármukkal
szomszédos negyedik él, ami nyilvánvalóan
lehetetlen.
Tehát van három élünk,
e
1
,
e
2
és
e
3
, melyek háromszöget alkotnak úgy,
hogy a megfelelő
e
1
′
,
e
2
′
és
e
3
′
élek ugyanabból az
x
pontból indulnak.
e
1
=
u
2
,
u
3
,
e
2
=
u
1
,
u
3
,
e
3
=
u
1
,
u
2
,
e
i
′
=
x
,
y
i
i
=
1
,
2
,
3
.
A fenti pár szolgáltat egy megoldást:
G
1
=
{
u
1
,
u
2
,
u
3
}
,
{
e
1
,
e
2
,
e
3
}
≇
G
2
=
{
x
,
y
1
,
y
2
,
y
3
}
,
{
e
1
′
,
e
2
′
,
e
3
′
}
, de
L
G
1
≅
L
G
2
. Azt állítjuk, hogy nincsenek további
ilyen párok. Ha lenne, akkor
E
G
i
≥
4
lenne.
Legyen
e
4
∈
E
G
1
,
e
4
≠
e
1
,
e
2
,
e
3
. Feltehetjük, hogy
e
4
=
u
1
,
v
. Ekkor
e
4
′
=
σ
e
4
metszi
e
1
-et és
e
3
-at, így
e
4
′
=
y
2
,
y
3
. Mivel
G
1
≇
G
2
, van egy további
e
5
∈
E
G
élünk. Ismét feltehetjük, hogy metszi
e
1
,
e
2
,
e
3
és
e
4
egyikét. Nyilvánvaló, hogy
u
1
∉
e
5
.
Ha
e
5
nem metszi
e
4
-et, akkor metszi
e
1
-et és
e
2
-t (mondjuk).
e
5
′
=
σ
e
5
-nek metszenie kell
e
1
′
-et és
e
2
′
-t, de
e
3
′
-at és
e
4
′
-et nem, ami lehetetlen. Ha
e
5
metszi
e
4
-et de
e
1
-et nem, akkor
e
5
′
-nek metszenie kell
e
4
′
-t, de
e
1
′
-et,
e
2
′
-t és
e
3
′
-et nem, ami megint lehetetlen. Tehát
e
5
=
u
2
,
v
vagy
u
3
,
v
; legyen mondjuk
e
5
=
u
2
,
v
, ekkor
σ
e
5
=
e
5
′
=
y
1
,
y
3
. Mivel
G
1
≇
G
2
, kell, hogy legyen egy hatodik
e
6
élünk is. Mint előbb, azt kapjuk, hogy
e
6
=
u
3
,
v
,
σ
e
6
=
y
1
,
y
2
. Így
G
1
≇
G
2
-ből az következik, hogy egy hetedik
élnek is kell lenni, de a fentihez hasonló érveléssel
adódik, hogy ez lehetetlen (111. ábra).
(c) Legyen
σ
:
L
G
1
→
L
G
2
egy nem triviális izomorfizmus. Ismét
legyenek
S
1
,
…
,
S
n
és
S
1
′
,
…
,
S
m
′
rendre a
G
1
és
G
2
pontjainak csillagai. Ha
σ
S
i
minden
1
≤
i
≤
n
-nek csillaga, akkor mint korábban is,
azt kapjuk, hogy
σ
egy triviális izomorfizmus. Ellenkező
esetben követhetjük az előző megoldást, de minden olyan
lépésnél, ahol azt mondtuk, hogy „mivel
G
1
≇
G
2
, kell lennie egy további élnek” meg
kell állnunk és adnunk kell egy példát. Így a 112.
ábrán látható párokat kapjuk. [H. Whitney,
Amer. J. Math.
54 (1932), 160–168.]
- 2. feladat F Ö
(a) Legyen
E
,
F
∈
E
K
n
r
. Ekkor
K
n
r
E
-től és
F
-től diszjunkt éleinek száma
Hasonlóan
K
n
r
α
E
-től és
α
F
-től diszjunkt éleinek száma
Tehát
Mivel
n
−
2
r
≥
r
, ebből az következik, hogy
E
∩
F
=
α
E
∩
α
F
.
Azt akarjuk megmutatni, hogy ugyanúgy, mint
15.1-ben, a bármely adott
x
pontot tartalmazó
r
-esek halmaza egy
β
x
pontot tartalmazó
r
-esek halmazába képződik le. Ez így
definiálja
V
K
n
r
egy
β
permutációját, ami
α
-t indukálja.
Tehát legyen
x
∈
V
K
n
r
, és
E
,
F
két olyan él, melyekre
E
∩
F
=
{
x
}
. Ekkor a fentiek szerint
α
E
-nek és
α
F
-nek van egy egyértelmű közös
β
x
pontja. Azt állítjuk, hogy ha bármely
A
∈
E
K
n
r
él tartalmazza
x
-et, akkor
α
A
tartalmazza
β
x
-et (és megfordítva).
Legyen
A
∈
E
K
n
r
,
x
∈
A
, és legyen
B
olyan
r
-es, melyre
B
∩
A
=
A
−
E
−
F
. Így
Mivel
azt kapjuk, hogy
Itt
α
B
∩
α
A
=
B
∩
A
,
α
A
∩
α
E
=
A
∩
E
,
α
A
∩
α
F
=
A
∩
F
, tehát (1)-ből az következik, hogy
azaz
β
x
∈
α
A
.
(b) Élesítjük az előző gondolatmenetet. Két olyan
adott
E
és
F
r
-estől diszjunkt
r
-esek száma, melyekre
E
∩
F
=
r
−
1
és ennél kevesebb, ha
E
∩
F
<
r
−
1
. Emiatt
E
∩
F
=
r
−
1
akkor és csak akkor, ha
α
E
∩
α
F
=
r
−
1
.
Most tegyük fel, hogy már minden
k
=
0
,
1
,
…
,
k
0
-ra tudjuk, hogy
E
∩
F
=
k
akkor és csak akkor, ha
α
E
∩
α
F
=
k
(
k
=
0
-ra biztosan tudjuk ezt). Ekkor
E
∩
F
=
k
0
+
1
akkor és csak akkor, ha
E
∩
F
>
k
0
, és van olyan
A
r
-es, melyre
E
∩
F
=
r
−
1
és
F
∩
A
=
k
0
; ez akkor és csak akkor áll, ha
α
E
∩
α
F
>
k
0
, és van olyan
A
r
-es, melyre
α
E
∩
α
A
=
r
−
1
és
α
F
∩
α
A
=
k
0
; ami viszont azzal ekvivalens, hogy
α
E
∩
α
F
=
k
0
+
1
.
Ez bizonyítja, hogy
E
∩
F
=
α
E
∩
α
F
bármely két
E
és
F
r
-esre.
Legyen
x
a
K
n
r
egy pontja,
E
és
F
pedig két olyan
r
-es
K
n
r
-ben, melyekre
E
∩
F
=
{
x
}
. Legyen
α
E
∩
α
F
=
{
β
x
}
, megmutatjuk, hogy
x
∈
A
-ból
β
x
∈
α
A
következik, vagy ami ezzel ekvivalens,
hogy
x
∉
A
-ból
β
x
∉
α
A
következik.
Legyen
x
∉
A
és indirekte tegyük fel, hogy
β
x
∈
α
A
. Legyen
A
∩
E
=
i
,
A
∩
F
=
j
,
d
=
V
K
n
r
−
A
−
E
−
F
. Ekkor
Azt is tudjuk, hogy
Tehát találunk olyan
B
r
-est, melyre
Tekintsük
α
B
-t. Nyilvánvaló, hogy
α
B
∩
α
A
=
∅
, tehát
β
x
∉
α
B
. Továbbá
és így
Emiatt
De
ami ellentmondás. [C. Berge, Hypergraph
Seminar, Lecture Notes in Math.
411, Springer
(1974), 1-12]
- 3. feladat F Ö
Legyen
E
és
F
két
r
-es,
E
∩
F
=
j
. Számoljuk meg a mind
E
-vel, mind
F
-fel szomszédos
r
-eseket. Azt kapjuk, hogy
(1) ha
j
<
2
i
−
r
, akkor nincsenek ilyen
r
-esek,
(2) ha
2
i
−
r
≤
j
, akkor a mind
E
-vel, mind
F
-fel szomszédos
r
-esek száma
(
i
-t és
r
-t rögzítettnek tekintjük).
Az
f
j
n
polinomok
j
=
2
i
−
r
,
2
i
−
r
+
1
,
…
,
r
−
1
,-re különbözőek, hiszen főtagjaik
Tehát ha
n
is elég nagy, akkor az
f
j
n
számok különbözőek
j
=
2
i
−
r
,
…
,
r
−
1
-re. Ebből az következik, hogy a
következő karakterizációt nyertük:
E
∩
F
=
j
akkor és csak akkor, ha a mind
E
-vel, mind
F
-fel szomszédos
r
-esek száma egyenlő
f
j
r
-rel.
Így ha definiálunk egy gráfot
L
i
K
n
r
pontjain úgy, hogy akkor kötünk össze
két pontot, ha közös szomszédaik száma
f
i
−
1
n
(jegyezzük meg, hogy
2
i
−
r
≤
i
−
1
), akkor
L
i
−
1
K
n
r
-t kapjuk. Emiatt
α
az
L
i
−
1
K
n
r
egy automorfizmusa. Hasonlóan tovább
folytatva azt kapjuk, hogy
α
az
L
0
K
n
r
automorfizmusa. De
L
0
K
n
r
=
L
K
n
r
¯
, így
α
az
L
K
n
automorfizmusa. 15.2-ből azt kapjuk,
hogy
α
-t
V
K
n
r
egy permutációja indukálja. [C. Berge;
uo.]
- 4. feladat F Ö
(a) Legyenek
S
1
,
…
,
S
n
a
G
pontjainak csillagai, és tekintsük a
következő hipergráfot:
Nyilvánvaló, hogy
L
H
≅
G
.
Általánosabban legyenek
C
1
,
…
,
C
m
olyan teljes gráfok, melyekre
C
1
∪
…
∪
C
m
=
G
. Minden
x
∈
V
G
-hez legyen
U
x
azon
C
i
-k halmazai, melyek tartalmazzák
x
-et és legyen
Ekkor
L
H
≅
G
. A természetes megfeleltetés
σ
U
x
=
x
, és triviálisan igazolható, hogy ez
izomorfizmus.
Megfordítva tegyük fel, hogy
L
H
≅
G
bármely
H
hipergráfra és legyen
σ
:
L
H
→
G
egy izomorfizmus. Minden
v
∈
V
H
-ra legyen
C
v
G
-nek a
σ
E
pontjai által feszített részgráfja,
ahol
v
∈
E
∈
E
H
. Nyilvánvaló, hogy
C
v
egy teljes részgráf,
⋃
v
∈
V
H
C
v
=
G
és ha
U
x
-szel jelöljük az
x
-et tartalmazó teljes
C
v
részgráfokat, akkor
(b)
n
szerinti indukcióval bizonyítjuk, hogy
a
G
n
2
∕
4
teljes gráf uniója.
n
=
2
-re ez nyilvánvaló. Legyen
n
>
2
,
x
és
y
pedig két szomszédos pont. A
G
−
x
−
y
gráf
t
=
n
−
2
2
4
=
n
2
4
−
n
+
1
teljes gráf,
C
1
,
…
,
C
t
és bizonyos izolált pontok
uniója.
Legyen
z
∈
V
G
−
x
−
y
. Ha
z
mind
x
-szel, mind
y
-nal szomszédos, akkor legyen
C
z
az
x
y
z
háromszög. Ha
z
vagy csak
x
-szel, vagy csak
y
-nal szomszédos, akkor legyen
C
z
a
z
-t
x
-hez, illetve
y
-hoz kötő él. Egyéb esetben legyen
C
z
=
{
z
}
. Továbbá legyen
C
0
az
x
,
y
él. A
C
0
és
C
z
z
∈
V
G
−
x
−
y
teljes gráfokat felvéve
teljes gráfot kapunk, melyek uniója
G
.
Tehát
G
élei lefoghatjuk
G
n
2
4
teljes gráffal, és így olyan
n
2
4
pontú hipergráfhoz jutunk, melynek
élgráfja
G
.
Az állítás éles, mint azt a
K
n
2
⋅
n
+
1
2
teljes páros gráf mutatja.
[P. Erdős–A. W. Goodman–L. Pósa,
Canad. J. Math.
18 (1966), 106–112.]
- 5. feladat F Ö
(a) Legyen
x
,
y
és
z
a
G
három olyan pontja, melyek bármely
kombinációját lehagyva
G
összefüggő marad (vagyis
x
,
y
és
z
a
G
egy feszítőfájának három végpontja; ha
G
egyetlen feszítőfája egy út, akkor
G
vagy kör, vagy út, és így
élgráf).
Legyen
G
−
x
≅
L
H
x
,
G
−
y
≅
L
H
y
,
…
,
G
−
x
−
y
≅
L
H
x
y
,
…
,
G
−
x
−
y
−
z
≅
L
H
x
y
z
. Ekkor
L
H
x
y
z
≅
L
H
x
y
−
e
z
a
z
-nek megfelelő
e
z
élekre. Minthogy
E
H
x
y
z
>
6
, ez azt jelenti, hogy az
L
H
x
y
z
és
L
H
x
y
−
e
z
közti izomorfizmust
H
x
y
z
-nek egy
H
x
y
-ba való beágyazása indukálja.
Hasonlóan kapunk sok más beágyazást (ezek a 113. ábrán
láthatók), melyek felcserélhetők az
L
H
x
y
, stb. és
G
megfelelő feszített részgráfjai közti
izomorfizmusokkal (113. ábra).
Mivel azt is tudjuk, hogy
H
x
y
z
-nak
H
x
-be,
H
y
-ba és
H
z
-be való beágyazása egyértelmű, ez a
diagram kommutatív. Így definiálhatjuk az összes
beágyazásokkal egymásra leképzett pontot, és vehetjük a
H
uniót.
H
élei természetes módon megfelelnek
G
pontjainak, és könnyen ellenőrizhető,
hogy ez a megfeleltetés egy izomorfizmus
L
H
és
G
között.
(b) Legyenek
G
1
,
…
,
G
k
azon egyszerű gráfok, melyek nem
élgráfok, de minden valódi feszített részgráfjuk az.
Mivel az előző feladat szerint legfeljebb 9 pontjuk
van, így véges sok ilyen gráf van.
Mármost ha
G
tetszőleges olyan gráf, mely nem
élgráf, akkor tartalmaz olyan nem szűkíthető feszített
részgráfot, mely nem élgráf, és ez
G
1
,
…
,
G
k
egyike. Megfordítva, ha
G
tartalmazza
G
1
,
…
,
G
k
egyikét, akkor nyilvánvaló, hogy nem
lehet élgráf.
- 6. feladat F Ö
(a) Tegyük fel, hogy a
G
=
L
H
gráf
a
,
b
,
c
és
d
pontjai
a
középpontú, 3 ágú csillagot alkotnak.
Ekkor az
a
él szomszédos
b
-vel,
c
-vel és
d
-vel; közülük kettő, mondjuk
b
és
c
az
a
-nak ugyanabból a végpontjából indul.
De ekkor
b
és
c
szomszédosak.
Legyenek
a
b
c
és
b
c
d
páratlan háromszögek, azt állítjuk,
hogy
a
,
b
és
c
a
H
ugyanazon pontjából indul. Indirekte
tegyük fel, hogy
a
,
b
és
c
egy
H
-beli háromszöget alkotnak. Definíció
szerint van egy olyan
x
pont, mely az
a
,
b
és
c
közül vagy eggyel, vagy mindhárommal
szomszédos. De ez lehetetlen, hiszen
x
-nek a
H
-beli
a
,
b
és
c
által alkotott háromszög egy pontjából
kell indulnia, így
x
az
a
,
b
és
c
közül kettővel szomszédos. Hasonlóan
d
is a
b
és
c
élek közös pontjából indul, amiből az
következik, hogy
a
és
d
szomszédosak.
(b) Feltehetjük, hogy
G
összefüggő, hiszen minden komponens
eleget tesz (i)-nek és (ii)-nek, és ha ezek élgráfok,
akkor
G
és az. Legyen
a
,
b
∼
c
,
d
az ötlettár szerinti. Tegyük fel, hogy
a
,
b
∼
c
,
d
∼
e
,
f
a
G
különböző élei, megmutatjuk, hogy
a
,
b
∼
e
,
f
(az ekvivalencia reláció többi
kritériuma triviálisan teljesül). Vegyük észre, hogy
{
a
,
b
,
c
,
d
}
teljes gráfot feszít. Tekintsük
a
-t és
e
-t (mondjuk),
a
≠
e
. Ha
a
=
c
vagy
d
, akkor
a
és
e
triviálisan szomszédosak, így tegyük
fel, hogy
a
≠
c
,
d
; hasonlóan
e
≠
c
,
d
. Ekkor
a
c
d
páratlan háromszög (ha
b
=
c
vagy
d
, ez azonnal adódik az ekvivalencia
definíciójából, ellenkező esetben
b
az
a
c
d
három pontjával szomszédos), hasonlóan
c
d
e
is páratlan háromszög, amiből
a
és
e
(ii) szerint szomszédosak. Ha
a
,
b
-nek és
e
,
f
-nek nincsen közös végpontja, akkor
azonnal levonhatjuk a következtetést, hogy
a
,
b
∼
e
,
f
. Tegyük fel, hogy
a
=
e
. Ha
c
vagy
d
az
a
-tól,
b
-től és
f
-től különböző, akkor az
a
b
f
háromszög három pontjával szomszédos,
úgyhogy ez a háromszög páratlan; ha
c
,
d
szintén éle ennek a háromszögnek,
akkor megint csak páratlannak kell lennie. Így
a
,
b
∼
e
,
f
ismét következik.
Legyenek
C
1
,
…
,
C
N
a
∼
reláció ekvivalencia-osztályai. Ezek
természetesen teljes gráfokat alkotnak. Megmutatjuk,
hogy
G
minden pontját ezen teljes gráfok
közül legfeljebb kettő tartalmazza, hacsak
G
nem a 114a, b és c ábrán látható
kivételes gráfok egyike.
Tegyük fel, hogy
x
∈
V
G
-t három teljes gráf tartalmazza, azaz
három nem-ekvivalens
x
-szel szomszédos
x
,
y
,
x
,
z
és
x
,
u
él van. (i) szerint
z
,
z
és
u
közül kettő szomszédos kell, hogy
legyen; legyen mondjuk
y
,
z
∈
E
G
. Mivel
x
y
z
nem páratlan háromszög,
u
-nak szomszédosnak kell lenni
y
és
x
egyikével, legyen mondjuk
u
,
y
∈
E
G
, és így
u
,
z
∉
E
G
. Ha
V
G
=
4
, akkor a 114a-t kapjuk.
Ha
G
nagyobb, van olyan
v
pont, mely szomszédos
x
,
y
,
z
és
u
egyikével. Az
x
y
z
és
x
y
u
háromszögeknek páros sok pontjával
kell szomszédosnak lennie, emiatt szomszédos lesz
x
és
y
egyikével. Legyen mondjuk
v
,
x
∈
E
G
(
x
és
y
szerepe szimmetrikus, mivel
y
,
x
,
y
,
z
és
y
,
u
nyilvánvalóan nem ekvivalensek). (i)
szerint
v
szomszédos
z
és
u
egyikével, mondjuk
u
,
v
∈
E
G
. Ismét abból, hogy
x
y
z
és
x
y
u
nem páratlan háromszögek, azt kapjuk,
hogy
v
,
y
∈
E
G
és
v
,
z
∈
E
G
. Ha
G
-nek csak öt pontja van, akkor a
114b-t kapjuk.
Nyilvánvaló, hogy
v
,
x
az
x
,
z
és
x
,
u
közül legalább az egyikkel nem
ekvivalens, legyen mondjuk
v
,
x
nem ekvivalens
x
,
u
-vel, vagyis
v
x
u
nem lehet páratlan háromszög; hiszen
ha az lenne, akkor egy olyan pont, amely a
v
x
u
pontjai közül páratlan sokkal
szomszédos, a
v
x
z
,
x
y
z
és
x
y
u
háromszögek egyikének páratlan sok
pontjával lenne szomszédos, mint az könnyen igazolható.
Tehát
y
,
z
,
u
és
v
szerepe szimmetrikus.
Tegyük fel, hogy
G
-nek van egy további
w
pontja, mely
x
,
y
,
z
,
u
és
v
egyikével szomszédos.
w
nem lehet szomszédos
x
-szel; hiszen ekkor
y
,
v
egyikének ugyanúgy, mint
z
és
u
egyikének szomszédosnak kellene lenni
w
-vel; legyen mondjuk
y
,
w
,
z
,
w
∈
E
G
, ekkor
x
y
z
páratlan, ami ellentmondás. Tehát
w
szomszédos (mondjuk)
y
-nal, de
x
-szel nem. Így az következik, hogy
szomszédos
u
-val,
v
-val és
z
-vel is. Tehát ha
G
-nek 6 pontja van, akkor 114c-t
kapjuk.
Figyeljük meg, hogy
x
,
…
,
w
által feszített élek között nem lehet
két ekvivalens, így
x
,
…
,
w
szerepei szimmetrikusak. Emiatt az
előbbi bekezdésből az is adódik, hogy nem lehet több
pont szomszédos az
x
,
…
,
w
pontok egyikével sem, vagyis valóban
csak a 114. ábra három gráfját kaphatjuk.
A bizonyítást most már könnyű befejezni. Ha
G
a 114. ábra három gráfjának egyike,
akkor élgráfja 114a
′
, b
′
és c
′
ábra megfelelő gráfjának. Ellenkező
esetben
G
lefedhető él-diszjunkt teljes
részgráfokkal úgy, hogy minden pontot ezek közül
pontosan kettő tartalmaz (ha szükséges, felveszünk
néhány egypontú gráfot). Ugyanúgy, mint 15.4a-ban,
ebből az következik, hogy
G
élgráf. [A. M. van Roof és
H. S. Wilf, Acta Math. Hung.
16 (1965),
263–269.]
(c) Azt állítjuk, hogy
G
akkor és csak akkor élgráfja valamely
egyszerű gráfnak, ha nem tartalmazza feszített
részgráfként a 115. ábrán látható gráfok egyikét
sem.
Az azonnal látszik, hogy ezek a gráfok nem
élgráfok, hiszen nem tesznek eleget az (a) rész (i)
vagy (ii) feltételének. Megfordítva tegyük fel, hogy
G
nem élgráf. Ekkor vagy tartalmazza a 3
ágú csillagot feszített részgráfként, vagy nem tesz
eleget (ii)-nek, azaz vannak olyan
a
,
b
,
c
és
d
pontok, melyekre
a
b
c
és
b
c
d
páratlan háromszögek és
a
és
b
nem szomszédosak. Legyenek
e
és
f
olyan pontok, melyek rendre az
a
b
c
és
b
c
d
páratlan sok pontjával szomszédosak.
Ekkor meg kell különböztetnünk az alábbi eseteket:
e
=
f
vagy
e
≠
f
; a megfelelő háromszög mely pontjai
szomszédosak
e
-vel és
f
-fel. Ezen esetek végiggondolása
egyszerű, de hosszadalmas; a 115. ábrán látható
gráfokat eredményezik. A részleteket az olvasóra
hagyjuk. [L. W. Beineke]
- 7. feladat F Ö
15.4-ből tudjuk, hogy egy gráf akkor és csak
akkor élgráfja 3-uniform, többszörös éleket nem
tartalmazó hipergráfnak, ha élei lefedhetők teljes
részgráfokkal úgy, hogy minden pontot ezek közül három,
és minden élt legfeljebb kettő tartalmaz.
Tegyük fel, hogy a 20. ábrán látható gráf élgráf,
vagyis létezik ilyen teljes részgráfokkal való
lefedése. Nyilvánvaló, hogy
x
0
,
z
1
-nek és
y
0
,
z
1
-nek maguknak is teljes részgráfoknak
kell lenni. Mivel
z
1
-et csak három teljes gráf
tartalmazza,
z
1
,
x
1
és
y
1
ezek egyike kell, hogy legyen.
Hasonlóan
u
1
,
x
1
és
y
1
is a fedő teljes részgráfok egyike.
Tehát
x
1
,
y
1
-et már tartalmazza két teljes fedő
részgráf, így
x
1
,
z
2
és
y
1
,
z
2
maguk is teljes fedő részgráfok
lesznek. Innentől kezdve az érvelés periodikusan
ismétlődik, míg azt nem kapjuk, hogy
x
n
,
z
n
+
1
és
y
n
,
z
n
+
1
maguk is fedő teljes részgráfok. Mivel
nyilvánvaló, hogy
x
n
+
1
,
z
n
+
1
és
y
n
+
1
,
z
n
+
1
is azok,
z
n
+
1
-t közülük négy tartalmazza, ami
ellentmondás.
Hagyjuk el
G
egy pontját. Alapvetően négyfajta pont
van:
x
i
(vagy
y
i
),
z
i
,
u
i
,
v
i
(vagy
w
i
). A 116. ábra mutatja, hogy hogyan
kell
G
−
t
-t részgráfokra osztani, ha
t
=
x
i
,
z
i
,
u
i
,
v
i
. [L. Nickel]
- 8. feladat F Ö
(a) Lásd 117. ábra.
(b) Ez csak átfogalmazása annak a
következménynek, melyet 6.69-ből vontunk le.
- 9. feladat F Ö
(a) Legyen
e
1
=
x
,
y
és
e
2
=
x
,
z
a
G
1
két szomszédos éle; megmutatjuk, hogy
ψ
e
1
és
ψ
e
2
szintén szomszédosak. Ha
e
1
és
e
2
párhuzamosak, akkor nyilvánvaló, hogy
ψ
e
1
és
ψ
e
2
is azok. Mivel
G
1
−
x
2-szeresen összefüggő, tartalmaz egy
y
-on és
z
-n áthaladó
C
x
kört, ha
y
≠
z
. Ekkor
ψ
C
egy kör
G
2
-ben. Mivel
C
+
e
1
más kört nem tartalmaz,
ψ
C
+
ψ
e
1
sem. Emiatt
ψ
e
1
nem húrja
ψ
C
-nek, vagyis van egy
u
végpontja, mely nincs rajta
ψ
C
-n. De
C
+
e
1
+
e
2
tartalmaz egy
e
1
-en és
e
2
-n áthaladó
C
′
kört. Így
ψ
C
′
⊆
ψ
C
+
ψ
e
1
+
ψ
e
2
egy
ψ
e
1
-t és
ψ
e
2
-t tartalmazó kör
G
2
-ben. Tehát
ψ
C
′
-nek van egy
u
-val szomszédos
≠
ψ
e
1
éle. Ennek az élnek
ψ
e
2
-nek kell lenni. Így
ψ
e
1
és
ψ
e
2
szomszédosak.
(b) Legyen
x
∈
V
G
1
, és legyenek
e
1
,
…
,
e
k
az
x
-szel szomszédos élek. Ekkor
ψ
e
1
,
…
,
ψ
e
k
páronként metszik egymást, és nincsen
köztük három, melyek háromszöget alkotna. Tehát van egy
η
x
pont, melyet
ψ
e
1
,
…
,
ψ
e
k
mindegyike tartalmaz. Az
η
x
pont egyértelmű; hiszen ha egy
u
≠
η
x
szintén
ψ
e
1
,
…
,
ψ
e
k
-be tartozna, akkor
ψ
e
1
,
…
,
ψ
e
k
párhuzamosak lennének; így
e
1
,
…
,
e
k
is párhuzamosak lennének, vagyis
x
-nek egyetlen szomszédja lenne, ami
lehetetlen, minthogy
G
3-szorosan összefüggő. Tehát
η
jól definiált. Legyen
u
∈
V
G
2
és legyenek
f
1
,
…
,
f
k
az
u
-val szomszédos élek. Mint az előbb,
most is van egy egyértelmű
x
∈
V
G
1
pont, melyet
ψ
−
1
f
1
,
…
,
ψ
−
1
f
k
tartalmaz. Ekkor
η
x
-et tartalmazza
f
1
,
…
,
f
k
, és így
u
=
η
x
. Emiatt
η
x
egyértelmű. Hasonlóan adódik az is,
hogy kölcsönösen egyértelmű. Azt is tudjuk, hogy ha
x
,
y
=
e
∈
E
G
, akkor
η
x
és
η
y
a
ψ
e
végpontjai. Emiatt
η
izomorfizmus. [H. Whitney,
Amer. J. Math.
54 (1932), 160–168.]
- 10. feladat F Ö
Ha
r
=
2
, akkor az állítás triviális. Tegyük
fel, hogy
r
>
2
. Legyen
v
illetve
v
′
az
x
r
-hez illetve
x
r
′
-höz legközelebbi olyan pont, melynek
foka legalább 3. Hagyjuk el
T
-ből
x
r
-t és az
x
r
-t
v
-vel összekötő út minden belső
pontját; hagyjuk el
T
′
-ből
x
r
′
-t és az
x
r
′
,
v
′
-út minden belső pontját. Így két fát
kapunk,
T
1
-et és
T
1
′
-t, rendre az
x
1
,
…
,
x
r
−
1
és
x
1
′
,
…
,
x
r
−
1
′
végpontokkal. Nyilvánvaló, hogy az
x
i
és
x
j
közti távolság azonos
T
-ben és
T
1
-ben
1
≤
i
<
j
≤
r
−
1
, és hasonló állítás igaz
T
′
-re és
T
1
′
-re. Tehát az indukciós feltétel miatt
T
1
≅
T
1
′
, sőt, létezik olyan
ϕ
izomorfizmus, melyre
ϕ
x
i
=
x
i
′
.
Megmutatjuk, hogy
ϕ
v
=
v
′
. Tekintsük az egyértelmű
ϕ
v
,
v
′
-utat és terjesszük ki egy
x
i
′
-t
1
≤
i
<
j
≤
r
−
1
x
′
-vel összekötő úttá. Ekkor
míg
Így a feltétel szerint
d
x
i
,
v
=
d
x
i
′
,
v
′
, amiből az adódik, hogy
v
′
=
ϕ
v
. Ebből az is következik, hogy
d
x
r
,
v
=
d
x
r
′
,
v
′
; hiszen
és a bal oldalak a feltétel szerint
azonosak. Mármost
ϕ
nyilvánvalóan kiterjeszthető egy
T
és
T
′
közötti izomorfizmussá.
[E. A. Smolenskii, Zhurnal
Vychisl. Mat. i Matem. Fiz. (1962),
371–372.]
- 11. feladat F Ö
(a) Legyen
P
i
j
az (egyértelmű)
x
i
,
x
j
-út
T
-ben. Legyen
Q
az (egyértelmű)
P
i
j
,
x
k
-út és jelöljük
v
-vel a kezdőpontját. Ekkor
nyilvánvaló, hogy
ami (a)-t bizonyítja.
Tekintsük a
P
i
j
és
P
k
l
utakat. Lehet 0, 1, vagy legalább 2
közös pontjuk. Először tegyük fel, hogy nem metszik
egymást, ekkor legyen
Q
a
P
i
j
,
P
k
l
-út
u
∈
V
P
i
j
és
v
∈
V
P
k
l
végpontokkal. Legyen
R
i
és
R
j
az
x
i
,
u
, illetve
x
j
,
u
-út,
R
k
és
R
l
pedig az
x
k
,
v
, illetve
x
l
,
v
-út
T
-ben. Így
Tehát
ami ebben az esetben bizonyítja a (b) pont
állítását.
Tegyük fel, hogy
P
i
j
-nek és
P
k
l
-nek pontosan egy
v
pontja közös. Ekkor a
v
-t
x
i
-vel,
x
j
-vel,
x
k
-val és
x
l
-lel összekötő utakat tekintve
ugyanúgy, mint előbb azt kapjuk, hogy
Végül ha
P
i
j
-nek és
P
k
l
-nek egynél több közös pontja van,
akkor vagy
P
i
k
és
P
j
l
, vagy
P
i
l
és
P
j
k
nem metszik egymást, és az indexek
felcserélésével az első esethez jutunk.
(c) Tegyük fel, hogy olyan
T
′
fát konstruáltunk az
x
1
,
…
,
x
r
−
1
végpontokkal, melyre
d
x
i
,
x
j
=
d
i
j
minden
1
≤
i
<
j
≤
r
−
1
esetén.
Legyen
x
i
és
x
j
a
T
′
két olyan pontja, melyekre
d
r
i
+
d
r
j
−
d
i
j
minimális. Legyen
v
a
T
′
-beli
x
i
,
x
j
-út azon pontja, melyre
és kössük
x
r
-t
v
-hez
1
2
d
r
i
+
d
r
j
−
d
i
j
hosszú úttal (ez lehetséges, mert ezek
a számok (a) szerint természetes számok). Azt állítjuk,
hogy az így kapott
T
fa eleget tesz
d
x
k
,
x
l
=
d
k
l
-nek minden
1
≤
k
<
l
≤
r
esetén. Ez triviális, hacsak nem
l
=
r
. Akkor is könnyű belátni
u
definíciójából, ha
k
=
i
vagy
k
=
j
, így tegyük fel, hogy
k
≠
i
,
j
.
(b) szerint a
d
i
j
+
d
r
k
,
d
i
r
+
d
j
k
és
d
j
r
+
d
i
k
számok közül kettő egyenlő és nem
kisebb a harmadiknál. Azt állítjuk, hogy
d
i
j
+
d
r
k
nem kisebb a másik kettőnél. Hiszen
tegyük fel, hogy
Ekkor
ami ellentmond
i
és
j
választásának. Tehát az
i
és
j
indexek megfelelő választására
Mármost
T
maga eleget tesz (b)-nek, sőt, a
T
-beli
x
r
,
x
k
-út és
x
i
,
x
j
-út biztosan találkozik. Így az előző
feladat megoldása miatt
ahol
i
0
,
j
0
az
i
,
j
egy permutációja. Mivel
d
x
i
,
x
j
=
d
i
j
,
d
x
i
0
,
x
r
=
d
i
0
r
, stb. (2) és (3) miatt feltehetjük,
hogy
i
0
=
i
,
j
0
=
j
, és ekkor (2) és (3) azt adja, hogy
[K. A. Zaretskii,
Usp. Matem. Nauk.
20 (1965), 94–96.]
- 12. feladat F Ö
(a) A
2
l
szám
{
a
i
+
a
j
:
1
≤
i
<
j
≤
n
}
-ben pontosan
-szer fordul elő, ha
l
páratlan és
-szer, ha
l
páros.
{
b
i
+
b
j
:
1
≤
i
<
j
≤
n
}
-ben pontosan
-szer fordul elő, ha
l
páratlan és
-szer, ha
l
páros. Tegyük fel, hogy pl.
l
páratlan, ekkor azt kell igazolnunk,
hogy
vagy ami ezzel ekvivalens,
ami az 1.42d azonosságból következik.
(b) Tegyük fel, hogy
{
a
i
+
a
j
:
1
≤
i
<
j
≤
n
}
=
{
b
i
+
b
j
:
1
≤
i
<
j
≤
n
}
, de
{
a
i
:
1
≤
i
≤
n
}
≠
{
b
i
:
1
≤
i
≤
n
}
. Megmutatjuk, hogy
n
a 2 hatványa. Feltehetjük, hogy
a
i
és
b
i
≥
0
, hiszen minden
a
i
-hez és
b
i
-hez konstanst hozzáadva a feltétel
érvényes marad. Legyen
Ekkor
tehát
Az utolsó azonosságba
x
=
1
-et akarunk helyettesíteni, mivel
ekkor a bal oldalon
2
n
áll. De
x
=
1
gyöke
f
x
−
g
x
-nek; tehát
Így
és
ami bizonyítja az állítást.
[J. Selfridge–E. G. Straus,
Pac. J. Math.
8 (1958), 847–856.]
- 13. feladat F Ö
Azt az általánosabb állítást bizonyítjuk, hogy ha
(ahol
c
i
1
,
…
,
c
i
k
≠
c
j
1
,
…
,
c
i
k
ha
i
≠
j
) az
s
1
,
…
,
s
k
≥
0
bármely választására eltűnik, akkor
α
1
=
…
=
α
M
=
0
. A feladat állítása
h
=
f
−
g
-t véve adódik.
Legyenek
c
1
,
…
,
c
p
a
c
i
k
1
≤
i
≤
N
különböző értékei. Ekkor
ahol
h
i
ugyanolyan formájú, mint
h
.
x
i
=
h
i
s
1
,
…
,
s
k
−
1
választással
Azt állítjuk, hogy az egyenletrendszer
determinánsa nem nulla. A
formulát használjuk, ahol
n
k
a Stirling partíciós számokat jelöli
(lásd 1.7). Az (4) egyenletrendszer determinánsának
i
+
1
-edik sorát szorozzuk
i
!
-sal, majd adjuk hozzá
j
i
-szer az
i
+
1
-edik sort a
j
+
1
-edik sorhoz
j
=
1
,
…
,
p
−
1
;
i
=
j
−
1
,
…
,
0
. Így azt kapjuk, hogy
Tehát (4)-nek csak triviális megoldása van
x
1
,
…
,
x
p
-re, vagyis
h
i
s
1
,
…
,
s
k
−
1
=
0
a nem-negatív
s
1
,
…
,
s
k
−
1
egészek bármely választására.
k
szerinti indukcióval (
k
=
0
-t tekinthetjük igaznak) azt kapjuk,
hogy minden
h
i
s
1
,
…
,
s
k
−
1
együttható nulla. Tehát
h
s
1
,
…
,
s
k
minden együtthatója is.
- 14. feladat F Ö
Vizsgáljuk a következő kifejezést:
Itt minden élt minden végpontjaitól
különböző
x
,
y
párnál megszámolunk, így
Ebből az következik, hogy
E
G
1
=
E
G
2
. Nézzük az alábbi kifejezést:
ahol
x
0
rögzített. Ha
e
egy
x
0
-lal szomszédos él, akkor
e
-t itt nem számoltuk; ellenkező
esetben
V
−
3
-szor számoltuk. Tehát
az
x
0
foka
G
i
-ben. Mivel ez az érték azonos
i
=
1
és 2-re,
d
G
1
x
0
=
d
G
2
x
0
.
Végül
ahol
ɛ
i
x
,
y
az
x
,
y
-élek száma
G
i
-ben. Mivel a többi tag nem függ
i
-től, azt kapjuk, hogy
ɛ
1
x
,
y
=
ɛ
2
x
,
y
, vagyis
G
1
és
G
2
azonosak.
- 15. feladat F Ö
(a) Legyen
H
1
és
H
2
két kör, melyekre
V
H
1
=
V
H
2
=
V
. Ekkor
H
1
−
x
egy
V
−
2
hosszú út,
H
2
−
x
szintén. Így
H
1
−
x
≅
H
2
−
x
minden
x
∈
V
-re, de természetesen
H
1
és
H
2
nem szükségképpen azonosak. Tehát az
állítás hamis.
(b) Legyen
G
i
−
x
-nek
f
H
,
G
i
−
x
darab
H
-val izomorf részgráfja. Képezzük a
következő összeget:
Ekkor
G
i
minden
H
-val izomorf részgráfját
V
−
V
H
-szor számoltuk, így
Mivel a feltétel szerint
V
>
V
H
, és a bal oldal
i
=
1
és 2 esetén ugyanaz, azt kapjuk, hogy
mint állítottuk. Ugyanígy érvelhetünk
feszített részgráfok esetén is.
(c) Először tegyük fel, hogy
G
1
egy izolált pontból és egy
V
−
1
pontú
H
összefüggő komponensből áll. Ekkor
G
2
-nek van
H
-val izomorf
H
′
feszített részgráfja az előző állítás
szerint. Minthogy megint az előző állításból tudjuk,
hogy
E
G
1
=
E
G
2
, az is következik, hogy
G
2
-nek nincsenek
H
′
-n kívüli élei, vagyis
G
2
H
′
-ből és egy izolált pontból áll. Tehát
G
1
≅
G
2
.
Megfordítva, ha
G
2
-nek van egy
V
−
1
pontú komponense, akkor hasonlóan
G
1
≅
G
2
. Tehát minden esetben a
G
1
és
G
2
olyan
H
-val izomorf komponenseinek száma,
melyekre
V
H
=
V
−
1
, azonos.
Tegyük fel, hogy ez minden olyan összefüggő
H
gráfra igaz, melyre
V
>
V
H
>
k
. Legyen
V
H
=
k
.
G
i
H
-val izomorf komponensei számának
meghatározásához megszámoljuk
G
i
H
-val izomorf feszített részgráfjait és
levonjuk a
G
i
nagyobb komponensei
H
-val izomorf feszített részgráfjainak
számát. Az előző feladat és az indukciós feltétel
szerint ez a szám azonos lesz
i
=
1
és 2 esetén.
Tehát
G
1
-nek és
G
2
-nek ugyanannyi komponense izomorf
bármely adott
H
-val, így
G
1
≅
G
2
. [P. J. Kelly, Pacific
J. Math. 7
(1957), 961–968.]
- 16. feladat F Ö
(a) Először megjegyezzük, hogy mivel
T
1
és
T
2
végpontjai azonosak. Legyen
W
ezen végpontok halmaza.
Ha
W
=
2
, akkor
T
1
is és
T
2
is egy út, tehát
T
1
≅
T
2
. A következőkben feltesszük, hogy
W
≥
3
.
Legyen
P
tetszőleges
T
1
-beli maximális út és
x
egy nem
P
-re eső végpont. Ekkor
T
2
−
x
≅
T
1
−
x
⊇
P
-ből következik, hogy
T
2
is tartalmaz ugyanilyen hosszú utat.
Így
T
2
átmérője legalább akkora, mint
T
1
átmérője. Minthogy ez megfordítva is
igaz, így átmérőjük azonos kell, hogy legyen,
mindkettőnek
d
.
(b) A páros
d
átmérő esetét tárgyaljuk (a páratlan
eset egyszerűbb). Legyen
c
i
a
T
i
fa középpontja. Feltehetjük, hogy
d
>
2
, hiszen ha
T
i
csillag, akkor tartalmaz
n
−
1
fokú pontot, és így a másik fa is
csillag.
1
∘
Először tegyük fel, hogy
T
i
−
x
átmérője minden
x
végpontra
d
.
Határozzuk meg a
T
i
azon
c
i
-hez kapcsolódó ágainak
m
i
D
számát, melyek izomorfak egy adott
D
-fával, melynek „gyökere” (azaz egy
c
i
-hez kapcsolódó pontja) is adott.
„Visszafelé” indukcióval bizonyítjuk, hogy
m
1
D
=
m
2
D
. Ha
V
D
≥
V
, ez triviálisan igaz.
Számoljuk meg, hogy hányszor fordul elő a
T
i
−
x
,
x
∈
W
, középpontjához kapcsolva a
D
ág. Ekkor
T
1
−
x
≅
T
2
−
x
miatt ugyanazt a számoz kapjuk
i
=
1
,
2
-re.
T
i
−
x
-nek kétféle
D
-vel izomorf ága van; ezek vagy maguk
is
T
i
ágai, vagy
T
i
egy nagyobb ágából
x
elhagyásával állnak elő. A
T
i
−
x
gráfok
T
i
nagyobb ágaiból előálló
D
ágainak száma azonos
i
=
1
és 2-re, hiszen
T
1
és
T
2
nagyobb ágai ugyanazok. Emiatt a
T
i
−
x
gráfok azon
D
ágainak száma, melyek a
T
i
D
ágai, azonosak
i
=
1
és 2 esetén. Mivel
T
i
minden
D
ágát
W
−
l
-szer számoltuk, ahol
l
a
D
végpontjaiknak száma, ez bizonyítja,
hogy
m
1
D
=
m
2
D
. Tehát
m
1
D
=
m
2
D
bármilyen gyökerű
D
esetén igaz. Ebből az következik, hogy
T
1
≅
T
2
.
2
∘
Tegyük fel, hogy pontosan egy olyan
x
0
pont van, melyre
T
1
−
x
0
=
T
2
−
x
0
átmérője kisebb
d
-nél. Ekkor pontosan két olyan
c
i
-hez kapcsolódó
B
1
i
és
B
2
i
ág kell, hogy legyen
T
i
-ben, mely tartalmaz
d
2
hosszú utat; tetszőleges számú más ág
lehet.
B
1
i
pontosan egy pontot tartalmaz, mely
d
2
távolságra van
c
i
-től;
B
2
i
legalább két ilyen pontot
tartalmaz.
2
∘
(a) Először tegyük fel, hogy
B
1
1
sem és
B
1
2
sem egyetlen út. Ekkor
B
2
i
a legnagyobb ág a
T
i
−
x
x
∈
W
−
{
x
0
}
fákban a középponthoz képest, melynek
legalább két pontja
d
2
távolságra van a gyökértől, és így
B
2
1
és
B
2
2
izomorf gyökeres fák. Tehát ugyanúgy,
mint
1
∘
-ben következik, hogy
T
1
-nek és
T
2
-nek a középponthoz kapcsolódó ágai
ugyanazok.
2
∘
(b) Tegyük fel, hogy
B
1
1
egyetlen út. Ekkor a
T
1
−
x
0
x
0
-lal szomszédos
x
1
végpontja rendelkezik azzal a
tulajdonsággal, hogy
T
1
−
x
0
minden
d
−
1
hosszú útja tartalmazza. Így
T
2
−
x
0
szintén tartalmaz olyan
x
2
végpontot, mely minden
d
−
1
hosszú útban előfordul. Mármost
x
0
T
2
-ben szomszédos kell, hogy legyen
x
2
-vel; hiszen egyébként
x
2
és
x
0
a
T
2
olyan végpontjai lennének, melyeket
minden
d
hosszú út tartalmaz, ami ellentmondás.
x
0
a
T
1
−
x
0
≅
T
2
−
x
0
megfelelő pontjaival van összekötve,
azaz
T
1
≅
T
2
.
3
∘
Az az eset, amikor
T
1
−
x
≅
T
2
−
x
átmérője
d
−
1
két
x
pontra (nyilvánvaló, hogy nem lehet
d
−
1
az átmérő 2-nél több végpontra),
analóg módon kezelendő. [uo.]
- 17. feladat F Ö
(a) Legyen
H
tetszőleges
n
pontú gráf és jelölje
G
→
H
azon
ϕ
:
V
G
→
V
H
leképezések számát, melyek kölcsönösen
egyértelműek és szomszédos pontokat szomszédosakba
képeznek. Ekkor
G
→
H
kifejezhető szita formulával a
következőképpen. Minden
S
⊆
E
G
-re jelöljük
G
S
-sel a
V
G
,
S
gráfot. Így az 5.18-ban szereplő
módszerhez hasonlóan
Speciálisan
Itt a
G
1
,
S
S
⊂
E
G
1
és
G
2
,
S
S
⊂
E
G
2
gráfok páronként izomorfak; ez
ugyanúgy adódik, mint 15.14b-ben. Továbbá
hiszen
G
1
-nek több éle van, mint
G
¯
2
-nek. Hasonlóan
Tehát (5)-ben és (6)-ben a jobb oldalon
ugyanazok a tagok szerepelnek. Ebből az következik,
hogy
Tehát
G
1
-nek van kölcsönösen egyértelmű
leképezése
G
2
-be. Mivel élszámuk azonos, így
G
1
≅
G
2
. [L. Lovász,
J. Comb. Theory
13 (1972), 309–310.]
(b) Feltehetjük, hogy
V
G
1
=
V
G
2
=
V
. Tekintsük a
V
egy véletlen
π
permutációját. Jelölje
A
i
B
i
azt az eseményt, hogy
e
i
-t egy nem szomszédos
G
1
-beli (
G
2
-beli) pontpárba képeztük le. Úgy,
mint 2.2a-ban, definiáljuk a következőket:
Jegyezzük meg, hogy úgy, mint 15.14b-ben,
vagy az (a) részben következik, hogy
Jelölje
η
és
ξ
az előforduló
A
i
-k és
B
i
-k számát. Ekkor 2.7b szerint
Így
Legyen itt
x
=
−
1
, és használjuk a triviális
relációkat, hogy
Ekkor (7)-ből azt kapjuk, hogy
a feltétel szerint. De a valószínűségi mező
definíciója szerint
σ
m
és
σ
m
′
racionális számok
n
!
nevezővel. Tehát egyenlőnek kell
lenniük.
Az (7) egyenlet konstans tagját véve azt kapjuk,
hogy
De ha
π
az azonosság, akkor
ξ
=
0
. Így
vagyis létezik olyan permutáció, ami minden
e
i
-t élbe képez. Ez izomorfizmus
G
1
és
G
2
között. [W. Müller,
J. Comb. Theory
B 22 (1977), 281–283.]
- 18. feladat F Ö
Azt fogjuk megmutatni, hogy ha
Y
=
k
−
1
, akkor
Legyenek
X
1
,
…
,
X
t
az
Y
-t tartalmazó
t
-esek
t
=
V
−
k
+
1
. Ekkor
ami egyszerű számolással adódik. Hasonlóan
Minthogy (8) és (9) bal oldala egyenlő és
V
−
k
−
r
+
1
>
0
, (8)-ből és (9)-ből az következik,
hogy
E
H
1
−
Y
=
E
H
2
−
Y
. Ez hasonlóan adódik minden olyan
Y
-ra, melyre
Y
≤
k
.
Legyen
T
⊆
V
,
T
=
r
.
T
-nek, mint
H
i
élének a multiplicitását akarjuk
kiszámítani; vagyis
H
i
azon éleinek számát akarjuk
meghatározni, melyek nem
H
i
−
t
-beliek egyetlen
t
∈
T
-re sem. A szita formulával ez a szám
Mivel
k
≥
r
, ez a szám ugyanaz lesz
i
=
1
és 2 esetén. Így
H
1
és
H
2
azonos. [V. Faber, Hypergraph
Seminar, Lecture Notes in Math.
411, Springer
(1974), 85–94.]
- 19. feladat F Ö
Jelölje
ν
i
X
az
X
⊆
V
multiplicitását mint
H
i
(
i
=
1
, 2) éle. Az állításból következik,
hogy
hiszen
ν
i
X
−
{
x
}
+
ν
i
X
az
X
−
{
x
}
él mutiplicitása
H
i
∖
x
-ben. Tegyük fel, hogy
H
1
≠
H
2
. Ekkor vannak olyan
X
⊆
V
halmazok, melyekre
ν
1
X
≠
ν
2
X
. Legyen
X
egy nem szűkíthető ilyen halmaz. Ekkor
(1) szerint
ν
1
X
−
{
x
}
≠
ν
2
X
−
{
x
}
minden
x
∈
X
-re. Ez csak akkor lehetséges, ha
X
=
∅
. Így feltehetjük, hogy
ν
1
∅
>
ν
2
∅
.
X
szerinti indukcióval bizonyítjuk, hogy
Ez (10)-ből könnyen adódik. Speciálisan
vagyis
V
minden páros részhalmaza
H
1
egy éle. Hasonlóan
V
minden páratlan részhalmaza
H
2
egy éle. [C. Berge, Hypergraph
Seminar, Lecture Notes in Math.
411, Springer
(1974), 1–12.]
- 20. feladat F Ö
(a) Jelölje
hom
A
,
B
és
epi
A
,
B
rendre az
A
-nek a
B
-be való homomorfizmusainak és
epimorfizmusainak (szürjektív homomorfizmusainak) a
számát. Először vegyük észre, hogy
(
∗
) Ha
epi
G
1
,
H
=
epi
G
2
,
H
minden
H
-ra, akkor
G
1
≅
G
2
.
Valóban,
epi
G
1
,
G
2
=
epi
G
2
,
G
2
>
0
és
epi
G
2
,
G
1
=
epi
G
1
,
G
1
>
0
, azaz
G
1
és
G
2
egymás epimorf képei. Mivel végesek,
így izomorfnak kell lenniük.
Tehát
hom
G
i
,
H
-t és
epi
G
i
,
H
-t akarjuk összehasonlítani.
Nyilvánvaló, hogy minden epimorfizmus homomorfizmus, és
egy homomorfizmus akkor és csak akkor epimorfizmus, ha
H
minden éle benne van a képben. Tehát
használhatjuk a szita formulát, amiből
Mivel a jobb oldalak
i
=
1
és 2 esetén tetszőleges rögzített
H
-ra azonosak, levonhatjuk a
következtetést, hogy
minden
H
gráfra igaz. (
∗
) szerint ebből az következik, hogy
G
1
≅
G
2
.
(b) Jelölje
mon
A
,
B
az
A
-nak a
B
-be való monomorfizmusainak (injektív
homomorfizmusainak) számát. Ismét
(
∗
) ha
mon
H
,
G
1
=
mon
H
,
G
2
minden
H
-ra, akkor
G
1
=
G
2
.
Valóban,
mon
G
2
,
G
1
=
mon
G
1
,
G
1
>
0
és
mon
G
1
,
G
2
=
mon
G
2
,
G
2
>
0
, azaz
G
1
-nek és
G
2
-nek van egymásba való monomorfizmusa,
ami miatt a végességükből következik, hogy
G
1
≅
G
2
.
mon
H
,
G
i
és
hom
H
,
G
i
összehasonlításához figyeljük meg,
hogy egy homomorfizmus akkor és csak akkor
monomorfizmus, ha nem azonosít pontpárokat. Legyen
U
′
x
1
,
y
1
,
…
,
x
k
,
y
k
a legkisebb olyan
ekvivalencia-reláció, melyre
x
i
és
y
i
azonos osztályba tartozik
i
=
1
,
…
,
k
, és bármely egyszerű
H
gráfra és bármely
V
H
-n értelmezett
U
′
ekvivalencia-relációra jelölje
H
∕
U
′
az
U
′
minden adott osztályában a pontok
azonosításával és az így keletkező többszörös élek
elhagyásával kapott egyszerű gráfot. Ekkor
mon
H
,
G
i
-t kifejezhetjük a szita formulával:
A jobb oldal itt is azonos
i
=
1
és 2 esetén, tehát
mon
H
,
G
1
=
mon
H
,
G
2
és (
∗
) bizonyítja az állítást.
[L. Lovász, Periodica Math. Hung.
1 (1971),
145–156.]
- 21. feladat F Ö
Legyenek
ϕ
,
ψ
:
H
→
G
1
homomorfizmusok, és
Ekkor könnyen igazolható, hogy
ξ
a
H
gráf egy homomorfizmusa
G
1
×
G
1
-be, és megfordítva,
H
minden
G
1
×
G
1
-be való homomorfizmusa egyértelműen
előáll így. Tehát
Így
és mivel
hom
H
,
G
i
≥
0
,
Ez minden
H
-ra igaz, tehát 15.19b-ből azt kapjuk,
hogy
G
1
≅
G
2
. [uo.]
- 22. feladat F Ö
(a) Próbáljuk ki
F
=
K
2
-t. Vegyük észre, hogy ha
v
∈
V
G
1
, akkor
v
,
x
∈
V
G
1
×
F
fokszámai azonosak
v
fokszámaival. Emiatt
G
1
és
G
2
fokszámai is azonosak kell, hogy
legyenek. Egy egyszerű nem izomorf pár azonos
fokszámsorozattal látható a 118. ábrán.
K
2
-vel direkt szorzatokat alkotva (
V
K
2
=
{
1
,
2
}
választással) minden esetben két
diszjunkt 6 hosszú kört kapunk, mint azt a 119. ábra
mutatja.
(b) Legyen
H
tetszőleges gráf. Az előző megoldáshoz
hasonló okok miatt
Azt akarjuk megmutatni, hogy
Ha
hom
H
,
F
′
=
0
, akkor (13) triviálisan igaz. Ha
hom
H
,
F
′
>
0
, akkor nyilvánvaló, hogy
hom
H
,
F
>
0
, így (12)-ből következik, hogy
hom
H
,
G
1
=
hom
H
,
G
2
, ami miatt (13) ismét adódik.
(c) Az ötlettárban megfogalmazott
G
⋅
H
∘
=
G
∘
×
H
∘
relációt könnyű igazolni. Ekkor
Jelölje
E
∘
az egy pontból és egy hurokélből álló
gráfot. Így
E
∘
a
H
∘
részgráfja, és így (b) szerint
(d) Az ötlettárban megfogalmazott állítás a
15.20b-hez hasonló érveléssel adódik, azzal az
eltéréssel, hogy
U
′
x
1
,
y
1
,
…
,
x
k
,
y
k
interpretációja a legkisebb
kongruencia-reláció, mely tartalmazza az
x
1
,
y
1
,
…
,
x
k
,
y
k
párokat.
Tegyük fel, hogy
G
1
,
G
2
és
F
véges csoportok és
Ha a
H
csoport homomorfizmusainak számát a
G
csoportba
hom
H
,
G
-vel jelöljük, akkor
minden véges
H
csoportra. Mivel
hom
H
,
F
≠
0
, ez azt adja, hogy
ami miatt
G
1
≅
G
2
.
Véges gyűrűkre a bizonyítás ugyanígy megy. Sőt,
ugyanígy megy bármely három
G
1
,
G
2
és
F
algebrára feltéve, hogy
F
-nek van 1 elemű részalgebrája.
[Kategóriákra való általánosítását lásd L. Lovász,
Acta Sci. Math.
33 (1972), 319–322.]