Maximálisan hány éle lehet egy n pontú, nem összefüggő gráfnak?

Mutassuk meg, hogy ha egy összefüggő gráf bármely köréből elhagyunk egy élt, akkor összefüggő marad.

Mutassuk meg, hogy ha egy n pontú gráfban n él van és összefüggő, akkor pontosan egy kör van benne.

Bizonyítsuk be, hogy egy n pontú körmentes gráfban van legalább n/2 független pont.

Bizonyítsuk be, hogy egy fában bármely két út közös része vagy üres, vagy egy út.

Bizonyítsuk be, hogy egy összefüggő gráf bármely két leghosszabb útjának van közös pontja.

Bizonyítsuk be, hogy egy fa összes leghosszabb útja átmegy egy ponton.

Egy fa bármely két x,y pontjának d(x,y) távolsága a köztük futó egyetlen út hossza. Melyik n pontú fára lesz a d(x,y)-k összege minimális?

Bizonyítsuk be, hogy egy gráf pontosan akkor 2-átmérőjű, ha
a) bármely két nem-szomszédos pontjának van közös szomszédja;
b) bármely pontjára igaz, hogy az x gyökerű szélességi faváz magassága legfeljebb kettő és van olyan x, amelyre pontosan kettő.

Ha egy tíz pontú gráfban minden pont foka legalább öt, akkor összefüggő. Írhatunk-e öt helyett kisebb számot is ebben az állításban? Igaz-e, hogy az ilyen gráf 2-átmérőjű?
Mit mondhatunk általában 2n pontú gráfra? Vagyis: melyik az a legkisebb k, amelyre igaz a következő: ha egy 2n pontú gráfban minden pont foka legalább k, akkor összefüggő? És melyik a legkisebb k, amely esetén az átmérője biztosan 2?

Adott n pont a síkon, semelyik kettő távolsága nem egyenlő. Definiáljuk e ponthalmaz távolsággráfját a következőképpen: Minden pontot összekötünk a hozzá legközelebbivel. Bizonyítandó, hogy az így kapott gráf
a) minden pontja legfeljebb ötödfokú;
b) körmentes;
c) tartalmaz üres n/2-est;
d) élszáma legalább n/2 és legfeljebb n–1;
Igaz-e ugyanez, ha minden pontot a tőle legtávolabbival kötünk össze?

Mutassuk meg, hogy egy gráf pontosan akkor nem összefüggő, ha pontjai két nem üres osztályba sorolhatók úgy, hogy a két osztály között nem fut él.

Mutassuk meg, hogy egy gráf és a komplementere közül legalább az egyik összefüggő. Hogyan élesíthető az állítás?

Bizonyítsuk be, hogy egy összefüggő gráf bármely körmentes részgráfja kiegészíthető a gráf favázává.

Anna és Béla a következő gráfjátékot játssza n ponton: felváltva húznak be éleket, és az veszít, aki kört zár be. Kinek van nyerő stratégiája?

Egy teniszverseny n résztvevője között egyértelmű erosorrend van: ha a megveri b-t és b megveri c-t, akkor a megveri c-t. Hány mérkőzéssel lehet megtudni, hogy ki a legerősebb játékos közöttük?

Az előző versenyen most ki szeretnénk választani a második legerősebbet is. Bizonyítsuk be, hogy ehhez n versenyző esetén n+élog₂nù–2 mérkőzés elég.

Most a legerősebbet és a leggyengébbet is szeretnénk megtalálni. Bizonyítsuk be, hogy ehhez elegendő 3n–2 mérkőzés.

a) Bizonyítsuk be, hogy ha egy körmentes gráfban van él, akkor legalább két elsőfokú pontja van.
b) Egy körmentes összefüggő gráfban pontosan két elsőfokú pont van. Mit mondhatunk a többi pont fokszámáról?
Ld. még: 41. feladat, 42. feladat

Egy n pontú gráfban nincs páratlan kör. Legfeljebb hány éle lehet?

Egy konvex szabályos n-szöget n–3 (páronként nem metsző) átlójával háromszögekre bontottunk. Bizonyítsuk be, hogy ha n legalább öt, akkor legalább két legrövidebb átlót használtunk.

Adottak a d₁, d₂, ..., d_n pozitív egészek. Bizonyítsuk be, hogy pontosan akkor van olyan n pontú fa, amelynek pontjai rendre d₁, d₂, ..., d_n fokúak, ha ∑d_i = 2n–2. (OKTV)

Egy háromszög alapú hasáb minden csúcsára egy-egy valós számot írtunk. Minden csúcson a vele szomszédos csúcsokon álló számok átlaga áll. Hány különböző szám szerepelhet a csúcsokon?

Mi a helyzet, ha hasáb helyett kockára kérdezzük ugyanazt, amit az előző feladat kérdez? És ha szabályos n oldalú hasábra? Milyen általános állítás mondható ki?

Adott n≥5 egész szám. Minden lehetséges módon számpárokat képeztünk belőlük, s vettük minden számpárban a számok összegét. Az így kapott (n²–n)/2 összeg közül legalább (n²–3n+4)/2 racionális. Bizonyítandó, hogy akkor az összes racionális. Következik-e a feltételből az is, hogy minden megadott szám is racionális?

Egy nxn-es négyzetrácson Első és Második a következő játékot játsszák: kezdetben minden él színtelen. Felváltva választanak egy még ki nem színezett élt és kékre színezik. (Élnek az olyan szakaszokat nevezzük, amelyek – legalább – egy kis négyzetet határolnak.) Az nyer, akinek először sikerül kört bezárnia. Kinek van nyerő stratégiája? És mi a helyzet akkor, ha az veszít, aki először zár be kört? (Kvant)

Egy országban bizonyos repülőterek között oda-vissza járatok közlekednek. Tudjuk a következőket: minden repülőtérrol legfeljebb öt járat indul. Minden repülőtérrol el lehet jutni minden másikra legfeljebb három átszállással. Maximálisan hány repülőtér lehet az országban?

a) Igaz-e, hogy ha egy összefüggő gráfban minden út legfeljebb 2k hosszú, akkor van olyan pontja, amelytől minden pont legfeljebb k távolságra van?
b) Igaz-e, hogy ha egy összefüggő gráfban minden út legfeljebb 2k hosszú, akkor bármely két pont távolsága legfeljebb k (vagyis az átmérője legfeljebb k)?

a) Legalább hány éle van egy n pontú 2-átmérőjű gráfnak?
b) Igaz-e, hogy ha egy 2-átmérőjű gráfban van elsőfokú pont, annak szomszédja telített pont?
c) Melyek azok a 2-átmérőjű gráfok, amelyekben nincs telített pont és három, négy vagy öt pontjuk van?
d) A páros gráfok közül melyeknek kettő az átmérője?
e) A körök közül melyeknek kettő az átmérője?
f)*: Egy n pontú 2-átmérőjű gráfban nincs telített pont. Bizonyítsuk be, hogy legalább (3n–5)/2 éle van.
g)*: Van-e olyan n pontú 2-átmérőjű, telített pont nélküli gráf, amelynek 2n–5 éle van?
h)*: Egy n pontú, 2-átmérőjű gráfban nincs telített pont. Minimálisan hány éle van?

Legyen G egy összefüggő n pontú gráf, amelynek legalább n éle van. Bizonyítsuk be, hogy van olyan f függvény, amely a gráf pontjain van értelmezve, értékkészlete a gráf élhalmazának része és minden x ponthoz egy olyan élt rendel, amelynek egyik végpontja éppen x.

a) Legyen X egy n elemű halmaz és legyenek F₁, F₂, …, F_n az X különböző részhalmazai. Bizonyítsuk be, hogy van olyan eleme X-nek, amelyet elhagyva minden F_i-bol továbbra is n különböző halmazt kapunk.
b) Egy n x n-es táblázat minden mezőjében egy betű áll. A táblázat bármely két sora különböző. Bizonyítsuk be, hogy a táblázatban van olyan oszlop, amelyet elhagyva a megmaradó táblázatnak nincs két egyező sora. (Kürschák-verseny 1979)

Egy n csúcsú összefüggő gráf minden élére egy valós számot írtunk, ezt nevezzük az él értékének. A gráf bármely útjának a súlya legyen a benne előforduló legnagyobb értékű él értéke. A gráf bármely x,y csúcsára jelölje f(x,y) az x-bol y-ba vezető legkisebb súlyú út súlyát. Bizonyítsuk be, hogy az f függvény legfeljebb n–1 különböző értéket vesz fel. (KöMaL F. 3209)

Legyen a G összefüggő gráf élszáma k. Bizonyítsuk be, hogy az élei megszámozhatók az 1, 2, 3, ..., k számokkal úgy, hogy minden olyan csúcs esetén, amelyből legalább két él indul ki, az illető csúcsból kiinduló összes élhez rendelt számok legnagyobb közös osztója egy. (NMDO 1991)

Legalább hány részre kell a tortát vágnunk, ha biztosítani akarjuk, hogy akár p, akár q vendégünk érkezik, mindkét esetben tudunk a vendégeknek egyenlő részeket adni, A) ha (p,q)=1; B) ha (p,q)=d. (Olimpiai válogató)

Mutassuk meg, hogy ha egy e élű, n pontú összefüggő gráfban e≤n, és a gráf nem kör, akkor van elsőfokú pontja.

Legyen G egy e élű, összefüggő, n pontú gráf. Hány olyan feszítő részgráfja van, amelyben minden pont foka páros?

a) Az I. fejezet 16. feladatában beláttuk, hogy ha egy 3n tagú társaságban bármely két embernek van közös ismerőse, akkor van közöttük n ember, aki együtt az összes többit ismeri, sot van n+1 ember, aki együtt mindenkit ismer. Mi a helyzet akkor, ha a feltételt némileg gyengítjük és csak annyit feltételezünk, hogy a társaság ismeretség-gráfja 2-átmérőjű, azaz csak annyit feltételezünk, hogy bármely két egymást nem ismerő embernek van közös ismerőse?
b) Az I. fejezet 26. feladatában élesítettük a 16. feladat állítását és bebizonyítottuk, hogy n embernél lényegesen kevesebb is van, akik együtt a társaság minden tagját ismerik. Mi a helyzet, ha a társaság ismeretség-gráfjáról csak annyit követelünk meg, hogy 2-átmérőjű?

Adott egy n pontú fa, n>2. Minimális számú új él behúzásával el akarjuk érni, hogy minden pont benne legyen egy körbe. Adjunk eljárást erre! Hány élt kell behúznunk? (Egy 2003-as számítástechnikai versenyfeladat alapján)

Van-e olyan összefüggő gráf, amelynek minden pontja elvágó pont?