- 1. feladat Ö M
Mutassuk meg, hogy
minden
G
gráfra fennáll.
- 2. feladat Ö M
(a) Legyen
G
1
,
G
2
két gráf, melyekre
V
G
1
=
V
G
2
. Mutassuk meg, hogy
(b) Ez a
V
G
1
=
V
G
2
feltevés nélkül is igaz.
- 3. feladat Ö M
Legyenek
d
1
≤
…
≤
d
n
egy egyszerű
G
gráf fokszámai és tegyük fel, hogy
d
k
≥
k
minden
k
≤
n
−
d
n
−
1
esetén. Ekkor
G
összefüggő.
- 4. feladat Ö M
Mutassuk meg, hogy
G
1
×
G
2
akkor és csak akkor összefüggő, ha
G
1
,
G
2
összefüggőek és egyikük tartalmaz páratlan
kört.
- 5. feladat Ö M
Minden
k
-reguláris páros (
k
≥
2
) összefüggő gráf kétszeresen összefüggő.
- 6. feladat Ö M
(a) Minden összefüggő
G
gráfnak van olyan pontja, melyet elhagyva a gráf
összefüggő marad. Mi a helyzet erősen összefüggő irányított gráfok
esetén?
(b) Legyen
G
olyan összefüggő gráf, mely nem tartalmaz
„cseresznyét”, vagyis két elsőfokú pontot, melyeknek közös
szomszédjuk van. Mutassuk meg, hogy elhagyhatunk két szomszédos
pontot az összefüggőség megsértése nélkül.
(c) Legyen
G
összefüggő gráf, mely se nem kör, se nem teljes
gráf. Mutassuk meg, hogy elhagyhatunk két nem szomszédos pontot a
G
összefüggőségének megsértése nélkül.
- 7. feladat Ö M
(a) Legyen
T
1
,
T
2
a
G
összefüggő gráf két feszítőfája. Bizonyítsuk be,
hogy
T
1
transzformálható
T
2
-be „közbülső” fák sorozatán keresztül, ha
mindegyik az előzőből egy él eltávolításával és egy másik
hozzáadásával áll elő.
(b) Tegyük fel, hogy
G
2-szeresen összefüggő. Ekkor ahhoz, hogy
T
2
-ből
T
1
-et kapjuk elég, ha a következő transzformációt
ismételten alkalmazzuk: eltávolítjuk azt az élt, mely a fa valamely
x
végpontjával szomszédos, majd
x
-et
G
valamely másik élén keresztül kapcsoljuk a
maradékhoz.
- 8. feladat Ö M
(a) Legyen
G
2-szeresen összefüggő
n
pontú gráf és
n
1
+
n
2
=
n
. Ekkor
V
G
-nek van olyan
{
A
1
,
A
2
}
partíciója, melyre
|
A
i
|
=
n
i
és
A
1
,
A
2
összefüggő részgráfokat alkotnak.
(b) Legyen
G
2-szeresen összefüggő nem páros
2
m
pontú gráf. Ekkor létezik
V
G
-n olyan
{
A
1
,
A
2
}
partíciója, melyre
|
A
i
|
=
m
és az
A
1
,
A
2
élek összefüggő feszítő részgráfot
alkotnak.
- 9. feladat Ö M
Egy irányított
G
gráf akkor és csak akkor erősen összefüggő, ha minden
X
⊂
V
G
,
X
≠
∅
halmazt legalább egy él hagy el.
- 10. feladat Ö M
Legyen
G
egy irányított gráf,
x
,
y
∈
V
G
és tegyük fel, hogy
G
éleit pirosra, zöldre és feketére színeztük. Ekkor
a következő két állítás közül pontosan egy igaz:
(i) Van olyan piros és fekete irányítatlan
P
x
,
y
-út
G
-ben, hogy
P
minden fekete éle
x
-től
y
felé mutat,
(ii) Van olyan
S
⊂
V
G
halmaz,
x
∈
S
,
y
∉
S
, hogy
S
-et és
V
G
−
S
-et egyik irányban sem köti össze piros él, és
nincsen
S
-ből
V
G
−
S
-be mutató fekete él.
- 11. feladat Ö M
(a) Tegyük fel, hogy az erősen összefüggő
G
irányított gráf összefüggősége megszűnik
≤
k
él eltávolításával. Bizonyítsuk, hogy ekkor
≤
k
él megfordításával is megszüntethető az összefüggősége.
(b) Tegyük fel, hogy
G
egy elvágóél nélküli irányított gráf, melyből
erősen összefüggő irányított gráfot kapunk legfeljebb
k
él összehúzásával. Ekkor legfeljebb
k
él megfordításával is kaphatunk erősen összefüggő gráfot.
(c) Ha egy
G
hurokmentes irányított gráf minden irányított körét megszüntethetjük legfeljebb
k
él eltávolításával, akkor legfeljebb
k
él megfordításával szintén megszüntethetjük őket.
- 12. feladat Ö M
Egy turnament akkor és csak akkor erősen
összefüggő, ha tartalmaz irányított Hamilton-kört.
- 13. feladat Ö M
Egy erősen összefüggő legalább 4 pontú
T
turnament tartalmaz legalább két olyan
x
pontot, melyekre
T
−
x
erősen összefüggő.
- 14. feladat Ö M
Legyen
G
egy irányított fa és
F
⊆
E
G
. Bizonyítsuk be, hogy van olyan
x
∈
V
G
pont, melyre az
x
-szel érintkező élek közül az
F
-beliek
x
-ben végződnek, míg a többi
x
-ben kezdődik.
- 15. feladat Ö M
Legyen
G
egy fa és legyen
olyan leképezés, hogy minden
x
,
y
∈
E
G
esetén
Mutassuk meg, hogy
ϕ
-nek van fix pontja vagy fix éle.
- 16. feladat Ö M
Ha a
G
fa részfái egy halmazának metszete nem üres, akkor
részfa.
- 17. feladat Ö M
(a) Ha
G
összefüggő gráf, akkor bármely két maximális
hosszú útjának van közös pontja.
(b) Ha
G
fa, akkor
G
összes maximális hosszú útjának van közös
pontja.
- 18. feladat Ö M
Ha
G
1
,
…
,
G
k
a
G
fa olyan részfái, hogy bármely kettő metszi
egymást, akkor van egy közös pontjuk. (Ez az előző feladat (b)
pontjának egy új bizonyításához vezet.)
- 19. feladat Ö M
Bizonyítsuk be, hogy egy összefüggő
G
gráfban az
x
,
y
pontok
d
x
,
y
távolsága ugyanúgy, mint a
x
-et és
y
-t összekötő utak
D
x
,
y
maximális hossza metrika. Vagyis:
(a)
d
x
,
y
≥
0
, egyenlőséggel akkor és csak akkor, ha
x
=
y
,
(b)
d
x
,
y
=
d
y
,
x
,
(c)
d
x
,
y
+
d
y
,
z
≥
d
x
,
z
, és hasonlóan
D
x
,
y
-ra.
- 20. feladat Ö M
Ha
G
egy fa, melynek
p
1
,
…
,
p
n
,
q
1
,
…
,
q
n
+
1
pontjai, akkor
- 21. feladat Ö M
(a) Legyen
d
˜
x
=
max
d
x
,
y
, ahol
x
és
y
egy
G
fa pontjai. Mutassuk meg, hogy
d
˜
x
minimumát egy ponton (
G
középpontján) vagy két szomszédos ponton
(
G
kettős középpontján) éri el.
(b) Mutassuk meg, hogy
d
˜
x
konvex függvény abban az értelemben, hogy ha
y
és
z
az
x
szomszédai, akkor
- 22. feladat Ö M
(a) Legyen
s
x
=
∑
y
d
x
,
y
, ahol
x
és
y
egy
G
gráf pontjai. Mutassuk meg, hogy
s
x
szigorúan konvex abban az értelemben, hogy ha
x
a fa egy pontja, és
y
és
z
az
x
szomszédai, akkor
(b) Mutassuk meg, hogy
s
x
minimumát vagy egy ponton (a súlypont) vagy
G
két szomszédos pontján veszi fel.
(c) Konstruáljunk olyan fát, melynek egy középpontja és egy
súlypontja van, és ezek egymástól való távolsága nagyobb mint
1000.
- 23. feladat Ö M
Határozzuk meg azokat az
n
pontú
G
fákat, melyekre
∑
x
,
y
d
x
,
y
maximális, ill. minimális.
- 24. feladat Ö M
Egy
n
pontú fában, melynek átmérője legalább
2
k
−
3
, legalább
n
−
k
db.
k
-hosszú út van.
- 25. feladat Ö M
Adva van
n
város, melyek között egy összefüggő
telefonhálózatot akarunk kiépíteni. Bármely két város közti
e
vonal
v
e
költsége ismert, és minimalizálni akarjuk a teljes
költséget. Így adott pontokon olyan fát keresünk, melyre az élek
költsége minimális. Mutassuk meg, hogy a következő algoritmussal a
kívánt eredményt érjük el: Az i-edik lépésben vegyük a már
kiválasztott élek által alkotott gráf egy
G
i
komponensét, és válasszunk egy minimális költségű
G
i
-t nem
G
i
-beli ponthoz kötő élt. Ha
G
i
az összes pontot tartalmazza, akkor megállunk.
- 26. feladat (Folytatás) Ö M
Mutassuk meg, hogy ha az élek költségei különbözők,
akkor az optimális fa egyértelmű.
- 27. feladat Ö M
Nevezzük a 2-szeresen élösszefüggő
G
gráf két élét ekvivalensnek, ha egyenlőek, vagy
elhagyva őket a gráf elveszti összefüggőségét. Mutassuk meg,
hogy
(a) ez egy ekvivalencia-reláció,
(b) egy ekvivalencia-osztály minden éle egy körön fekszik
(amely tartalmazhat más éleket is),
(c) egy
P
ekvivalencia-osztály éleit eltávolítva a megmaradó
gráf komponensei 2-szeresen élösszefüggőek,
(d)
G
−
P
komponenseit összehúzva egy kört kapunk.
- 28. feladat Ö M
Egy adott 2-szeresen élösszefüggő
G
gráfot „felépíthetünk” a következőképpen:
G
=
G
1
∪
…
∪
G
r
, ahol
G
1
kör és
G
i
+
1
vagy egy út, melynek pontosan a végpontjai közösek
G
1
∪
…
∪
G
i
-vel, vagy egy kör, melynek egy pontja közös
G
1
∪
…
∪
G
i
-vel (3. ábra).
- 29. feladat Ö M
Egy
G
gráf akkor és csak akkor irányítható úgy, hogy az
eredményül kapott
G
→
irányított gráf erősen összefüggő, ha
G
2-szeresen élösszefüggő.
- 30*. feladat Ö M
Egy élt akkor nevezünk egy
C
körhöz jól illeszkedőnek, ha vagy
C
-re esik, vagy nincsen
C
-vel közös pontja.
Legyen
e
1
,
…
,
e
k
egy 2-szeresen élösszefüggő
G
gráf független élei. Mutassuk meg, hogy létezik
olyan
C
kör, melyhez az
e
1
,
…
,
e
k
élek mind jól illeszkednek.
- 31. feladat Ö M
Mutassuk meg, hogy „az
e
és
f
élek egyenlőek vagy egy körre esnek” egy
ekvivalencia-reláció.
- 32. feladat Ö M
Egy
G
gráf következő tulajdonságai ekvivalensek:
(i)
G
2-szeresen összefüggő,
(ii)
G
bármely két pontja egy körre esik,
(iii)
G
bármely két éle egy körre esik,
G
-ben nincs izolált pont és
|
V
G
|
≥
3
.
- 33. feladat Ö M
Legyen
G
2-szeresen összefüggő gráf, mely nem kör. Ekkor van olyan
P
út
G
-ben, melynek minden belső pontja (ha van ilyen)
másodfokú, és éleit és belső pontjait elhagyva a megmaradó gráf
2-szeresen összefüggő.
- 34. feladat Ö M
Legyen
p
és
q
a 2-szeresen összefüggő
G
gráf két pontja. Mutassuk meg, hogy
G
irányítható úgy, hogy minden él rajta legyen egy
p
,
q
-úton.
- 35. feladat Ö M
Legyen
G
2-szeresen összefüggő gráf. Ekkor a következő
tulajdonságok ekvivalensek:
(i)
G
kritikusan 2-szeresen összefüggő,
(ii)
G
egyetlen körének sincs húrja.
- 36*. feladat Ö M
Legyen
G
kritikusan 2-szeresen összefüggő gráf. Mutassuk
meg, hogy
G
minden
C
körében van másodfokú pont.
- 37*. feladat Ö M
Legyen
G
kritikusan 2-szeresen összefüggő gráf. Hagyjunk el
G
-ből minden másodfokú pontot. Mutassuk meg, hogy
az így kapott
G
′
gráf nem összefüggő erdő.
- 38. feladat Ö M
Konstruáljunk kritikusan 2-szeresen összefüggő
G
gráfot úgy, hogy valamely
x
∈
V
G
távolsága minden másodfokú ponttól legalább 1000 legyen.
- 39*. feladat (Menger tétel) Ö M
Legyen
G
irányított gráf és
a
,
b
∈
V
G
. Bizonyítsuk be, hogy
(a) akkor és csak akkor létezik
k
él-diszjunkt
a
,
b
-út, ha
G
k
-szorosan élösszefüggő
a
és
b
között;
(b) akkor és csak akkor van
k
független
a
,
b
-út, ha
G
k
-szorosan összefüggő
a
és
b
között;
(c) analóg állítások érvényesek irányítatlan gráfokra.
- 40. feladat Ö M
Legyen
A
és
B
a
V
G
diszjunkt részhalmazai és tegyük fel, hogy minden
olyan
X
halmaznak, mely minden
A
,
B
-útból tartalmaz pontot legalább
k
eleme van. Mutassuk meg, hogy ekkor van
k
pont-diszjunkt
A
,
B
-út.
- 41. feladat Ö M
Fogalmazzuk meg és bizonyítsuk az Menger tétel
irányítatlan pontösszefüggőségi változatának (6.39b és
6.40) közös általánosítását.
- 42*. feladat Ö M
Legyen
B
⊂
V
G
és
a
∈
V
G
−
B
; tegyük fel, hogy adva van
k
független
a
,
B
-út,
P
1
,
…
,
P
k
, és
k
+
r
független
a
,
B
-út,
Q
1
,
…
,
Q
k
+
r
. Bizonyítsuk be, hogy léteznek olyan
1
≤
j
1
<
…
<
j
r
≤
k
+
r
és
R
1
,
…
,
R
k
a
,
B
-utak, ahol
R
i
és
P
i
azonos pontban végződik, hogy,
R
1
,
…
,
R
k
,
Q
j
1
,
…
,
Q
j
r
függetlenek.
- 43. feladat Ö M
Legyenek
a
,
b
és
c
a
G
különböző pontjai. Tegyük fel, hogy van
k
független
a
,
b
-út,
P
1
,
…
,
P
k
, és egy tőlük független
b
,
c
-út, valamint
k
(másik) független
a
,
b
-út,
Q
1
,
…
,
Q
k
és egy ezektől független
a
,
c
-út,
Q
0
. Mutassuk meg, hogy van
G
-ben
k
+
1
független
c
,
b
-út. (Próbáljuk meg elkerülni a Menger tétel
használatát.)
- 44. feladat Ö M
A Menger tétel használata nélkül határozzunk meg minden
G
gráfot, melynek van két olyan nem szomszédos
a
és
b
pontja, melyre
(i)
G
-ben legfeljebb
k
független
a
,
b
-út van, de
(ii) ha bármilyen új élt adunk
G
-hez, akkor a kapott gráfban legalább
k
+
1
független
a
,
b
-út lesz.
Vezessük le ebből a Menger tétel irányítatlan független út
változatát.
- 45. feladat Ö M
Legyen
G
irányított gráf és
a
,
b
∈
V
G
. Döntsük el, hogy a következő állítások
igazak-e:
(i) Ha bármely két útnak, melyek
a
és
b
egyikéből a másikba mennek, van közös éle, akkor
van olyan él, melyet ezen utak mindegyike tartalmaz.
(ii) Ha
G
k
-szorosan élösszefüggő
a
és
b
között, akkor
k
-szorosan élösszefüggő
b
és
a
között is.
(iii) Ha
G
k
-szorosan élösszefüggő
a
és
b
között és
b
és
a
között is, akkor van
k
a
,
b
-út,
P
1
,
…
,
P
k
és
k
b
,
a
-út,
Q
1
,
…
,
Q
k
, melyek kölcsönösen él-diszjunktak.
- 46. feladat Ö M
Tegyük fel, hogy
G
minden
x
≠
a
,
b
pontjának kifoka egyenlő a befokával és
d
G
+
a
−
d
G
−
a
=
k
>
0
. Bizonyítsuk, hogy
G
-ben van
k
él-diszjunkt
a
,
b
-út.
- 47. feladat Ö M
Ha
G
minden pontjának kifoka egyenlő a befokával, akkor
6.45-ből (i), (ii) és (iii) mindegyike igaz.
- 48. feladat Ö M
Legyen
G
egy gráf és
X
,
Y
,
Z
⊆
V
G
. Vezessük le a következő
egyenlőtlenségeket:
(a)
δ
G
X
∪
Y
+
δ
G
X
∩
Y
≤
δ
G
X
+
δ
G
Y
;
(b)
δ
G
X
−
Y
+
δ
G
Y
−
X
≤
δ
G
X
+
δ
G
Y
;
(c)
δ
G
X
−
Y
−
Z
+
δ
G
Y
−
Z
−
X
+
δ
G
Z
−
X
−
Y
+
δ
G
X
∩
Y
∩
Z
≤
δ
G
X
+
δ
G
Y
+
δ
G
Z
.
- 49*. feladat Ö M
Bizonyítsuk be, hogy minden kritikusan
k
-szorosan élösszefüggő gráfnak van
k
fokú pontja.
- 50. feladat Ö M
Legyen
G
egy
k
-szorosan élösszefüggő gráf és legyenek
F
1
,
…
,
F
m
az élek
k
elemű elvágóhalmazai. Bizonyítsuk be, hogy
G
−
F
1
∪
…
∪
F
m
-nek legfeljebb
2
m
összefüggő komponense van.
- 51*. feladat Ö M
Legyen
G
Euler-gráf,
x
∈
V
G
és tegyük fel, hogy
G
k
-szorosan élösszefüggő bármely két
u
,
v
≠
x
pont között. Ekkor van az
x
-nek két olyan
y
és
z
szomszédja[]
hogy ha elhagyjuk az
x
,
y
és az
x
,
z
élt, de behúzunk egy új
y
-t
z
-vel összekötő élt, a kapott gráf még mindig
k
-szorosan élösszefüggő bármely két
u
,
v
≠
x
pont között.
- 52*. feladat Ö M
Legyen
G
egy
2
k
-szorosan élösszefüggő,
2
k
-reguláris gráf. Bizonyítsuk, hogy
G
előáll a következő konstrukcióval:
I. Először felveszünk két pontot, és összekötjük őket
2
k
éllel.
II. Ha már megkonstruáltunk egy gráfot, kiválasztjuk
k
élét, felosztjuk őket egy-egy ponttal, és
azonosítjuk az új pontokat.
- 53*. feladat Ö M
Bizonyítsuk be, hogy a 6.51 feladat állítása nem
Euler-féle gráfok esetén is igaz, feltéve, hogy
k
≥
2
és
x
páros fokszámú.
- 54. feladat Ö M
(a) Legyen
G
tetszőleges gráf és legyen
G
→
a
G
egy irányítása. Ha
G
→
k
-szorosan élösszefüggő, akkor
G
2
k
-szorosan összefüggő.
(b)* Megfordítva, ha
G
2
k
-szorosan élösszefüggő, akkor létezik olyan
G
→
irányítása, mely
k
-szorosan összefüggő (6.29 általánosítása).
- 55. feladat Ö M
Legyenek
α
és
β
egész számok,
G
tetszőleges gráf, és
a
,
a
′
,
b
,
b
′
a
G
négy pontja. Keresünk olyan
P
1
,
…
,
P
α
a
,
a
′
-utakat, és olyan
Q
1
,
…
,
Q
β
b
,
b
′
-utakat, hogy
P
1
,
…
,
P
α
,
Q
1
,
…
,
Q
β
él-diszjunktak. Mutassuk meg, hogy a következő
feltételek szükségesek:
(
∗
) El kell hagynunk legalább
α
élt, hogy elválasszuk
a
-t
a
′
-től, legalább
β
élt, hogy elválasszuk
b
-t
b
′
-től, és legalább
α
+
β
élt, hogy elválasszuk
{
a
,
b
}
-t
{
a
′
,
b
′
}
-től vagy
{
a
,
b
′
}
-t
{
a
′
,
b
}
-től.
Példán keresztül mutassuk meg, hogy ezen feltételek nem
mindig elégségesek.
- 56*. feladat Ö M
Legyenek
a
,
a
′
,
b
és
b
′
egy
G
Euler-gráf pontjai, és
α
és
β
páros pozitív egészek. Tegyük fel, hogy az előző
feladatban megfogalmazott (
∗
) feltétel teljesül.
(a) Mutassuk meg, hogy
G
-nek van olyan
G
→
irányítása, melyre
(b) Bizonyítsuk be, hogy
G
tartalmaz
α
a
,
a
′
-utat és
β
b
,
b
′
-utat, melyek mind él-diszjunktak.
- 57. feladat Ö M
Konstruáljunk olyan 5-szörösen összefüggő
G
gráfot és ennek olyan
a
,
b
,
c
és
d
pontját, hogy minden
a
,
b
-útnak minden
c
,
d
-úttal van közös pontja.
- 58. feladat Ö M
Legyenek
A
és
B
egy
k
-szorosan összefüggő
G
gráf pontjainak olyan
k
-elemű halmazai, melyek elválasztják
a
-t és
b
-t. Mutassuk meg, hogy azon
A
∪
B
-beli pontok
C
halmaza, melyek
a
,
A
∪
B
-utak végpontjai, egy
a
-t és
b
-t elválasztó
k
-elemű halmaz.
- 59. feladat Ö M
Legyen
G
kritikusan
k
-szorosan összefüggő gráf és legyen
H
ennek
k
-szorosan összefüggő részgráfja. Mutassuk meg,
hogy
H
is kritikusan
k
-szorosan összefüggő.
- 60*. feladat Ö M
(a) Legyen
G
tetszőleges
k
-szorosan összefüggő gráf,
A
ennek egy
k
elemű lefogó halmaza,
G
1
a
G
−
A
egy komponense és tegyük fel, hogy
A
-t úgy választottuk, hogy
|
V
G
1
|
minimális. Mutassuk meg, hogy bármely
k
-elemű
B
lefogó halmazra vagy
V
G
1
⊆
B
vagy
V
G
1
∩
B
=
∅
. Továbbá az előbbi esetben
|
V
G
1
|
≤
k
2
.
(b) Minden kritikusan
k
-szorosan összefüggő
G
gráfnak van
k
fokú pontja.
- 61*. feladat Ö M
Legyen
G
egyszerű 3-szorosan összefüggő gráf és tegyük fel,
hogy az
e
él mindkét végpontja legalább 4 fokú. Ekkor
G
∕
e
és
G
−
e
közül az egyik 3-szorosan összefüggő.
- 62. feladat Ö M
Legyen
G
kritikusan 3-szorosan összefüggő gráf és
e
egy olyan éle, mely két legalább 4 fokú pontot köt
össze. Ekkor
G
∕
e
kritikusan 3-szorosan összefüggő gráf.
- 63. feladat Ö M
Ha
G
kritikusan 3-szorosan összefüggő gráf, akkor
minden köre tartalmaz legalább két 3 fokú pontot.
- 64. feladat Ö M
Tegyük fel, hogy a 3-szorosan összefüggő
G
gráf minden
e
élére
G
−
e
és
G
∕
e
nem 3-szorosan összefüggőek. Mutassuk meg, hogy
G
≅
K
4
.
- 65. feladat Ö M
Konstruáljunk kritikusan 3-szorosan összefüggő
gráfot és benne olyan
x
pontot, melyre minden
x
-től legfeljebb 1000 távolságra lévő pont foka
legalább 1000.
- 66. feladat Ö M
Egy
k
-szorosan összefüggő
G
gráfban bármely
k
pont egy körön van.
- 67*. feladat Ö M
Legyenek
e
1
,
e
2
és
e
3
egy 3-szorosan összefüggő
G
gráf független élei. Ekkor van
e
1
-et,
e
2
-t és
e
3
-at tartalmazó kör, kivéve, ha
e
1
,
e
2
és
e
3
vágást alkotnak.
- 68. feladat Ö M
Legyenek
a
,
b
,
x
1
,
…
,
x
k
egy
k
+
1
-szeresen összefüggő
G
gráf különböző pontjai. Bizonyítsuk be, hogy van olyan
a
b
-út, mely
x
1
,
…
,
x
k
-t tartalmazza.
- 69. feladat Ö M
Mutassuk meg, hogy egy egyszerű síkbarajzolható
3-szorosan összefüggő gráf
C
körének akkor és csak akkor van pontosan egy
hídja, ha
C
egy lap határa. Következésképpen a 3-szorosan
összefüggő egyszerű síkbarajzolható gráfok síkbaágyazása lényegében
egyértelmű.
- 70*. feladat Ö M
Minden 3-szorosan összefüggő
G
gráfban van olyan
C
kör, melynek pontosan egy hídja van.