Feladat: u és v két csúcs egy gráfban. A következõk ekvivalensek:

• van egy zárt vonal, amely mindkét csúcsot tartalmazza,
• van két éldiszjunkt uv vonal,
• van két éldiszjunkt uv út.

Feladat: Két csúcs a `kétszeres elérhetõség' relációban áll, ha az elõzõ feladatban leírt tulajdonsággal rendelkezik. Bizonyítsuk be, hogy a kétszeres elérhetõség egy ekvivalenciareláció.

Definíció: Egy gráf kétszeresen élösszefüggõ, ha összefüggõ és bármely élét elhagyva összefüggõ marad.

Feladat: Egy gráf akkor és csak akkor kétszeresen összefüggõ, ha bármely két csúcs kétszeresen elérhetõ relációban áll.

Definíció: Legyen G egy gráf, adjunk hozzá v₁, v₂, ..., v_k új csúcsokat, jelöljünk ki G-ben v₀ és v_k+1 csúcsokat. Kössük össze v_i és v_i+1-et i=0,1,2,...,k esetén. Az így kapott g' gráfra azt mondjuk, hogy fülragasztással kapjuk G-bõl. k=0 lehetséges, amikor is egyetlen él hozzáadása a fülragasztás. v₀=v_k+1 lehetséges, amikor is az új élek egy kör élhalmazát adják. Ha v₀ és v_k+1 két különbözõ csúcs, akkor az új élek egy út élhalmazát alkotják.

Feladat: A G' gráfot G-bõl kapjuk fülragasztással. Bizonyítsuk be, hogy G' akkor és csak akkor kétszeresen élösszefüggõ, ha G kétszeresen élösszefüggõ.

Feladat: Legyen R a G kétszeresen élösszefüggõ gráf egy kétszeresen élösszefüggõ részgráfja, amely nem a teljes G. Ekkor van olyan R' részgráfja G-nek, ami R-bõl egy fülragasztással kapható.

Feladat: G akkor és csak akkor kétszeresen élösszefüggõ, ha az egy pontú, nulla élû gráfból fülragasztásokkal kapható.

Feladat: Bizonyítsuk be, hogy egy kétszeresen élösszefüggõ gráf minden fülragasztással történõ felépítéséhez ugyanannyi fülragasztás operációra van szükségünk.

Definíció: Egy kétszeresen élösszefüggõ gráfot minimálisnak nevezünk, ha bármely élét elhagyva elveszti kétszeres élösszefüggõségét.

Feladat: Bizonyítsuk be, hogy egy minimális kétszeresen élösszefüggõ gráfban van másodfokú csúcs.

Feladat: Bizonyítsuk be, hogy egy legalább két pontú minimális kétszeresen élösszefüggõ gráfban van legalább két másodfokú csúcs, de több létezését nem állíthatjuk.

Feladat: Bizonyítsuk be, hogy egy minimális kétszeresen élösszefüggõ gráfban legalább |V| és legfeljebb 2|V|-2 él van.  

Feladat: Egy gráf két éle `kör-összefüggõ' relációban van, ha van olyan kör, amley mindkettõjüket tartalmazza vagy a két él egybeesik. Bizonyítsuk be, hogy ez a reláció ekvivalenciareláció.

Definíció: Egy gráf kétszeresen összefüggõ, ha összefüggõ és bármely csúcsát elhagyva összefüggõ marad, továbbá legalább 3 csúcsa van.

Feladat: Bizonyítsuk be, hogy G akkor és csak akkor kétszeresen összefüggõ, ha bármely két éle kör-összefüggõség relációban áll, továbbá legalább három pontú osszefüggõ gráf.

Feladat: Legyen G egy legalább három pontú összefüggõ gráf. Bizonyítsuk be, hogy a következõk ekvivalensek:

• kétszeresen összefüggõ, azaz bármely két különbözõ éle egy körön van,
• bármely két csúcsa egy körön van,
• bármely xy csúcshoz van két P₁ és P₂ xy út, amelyek belsõ ponthalmaza két diszjunkt halmaz.

Feladat: Bizonyítsuk be, hogy egy kétszeresen összefüggõ gráf egyben kétszeresen élösszefüggõ is. Megfordítva igaz a kapcsolat?

Feladat: Legyen G egy 3-reguláris gráf. Bizonyítsuk be, hogy G akkor és csak akkor kétszeresen összefüggõ gráf ha kétszeresen élösszefüggõ.

Definíció: A fülragasztásban egy fül nyilt, ha v₀ és v_k+1 különbözik, azaz a ragasztás alatt megjelenõ élek egy út élhalmazát alkotják.

Feladat: Bizonyítsuk be, hogy egy hurokél nélküli gráf akkor és csak akkor kétszeresen összefüggõ, ha felépíthetõ egy legalább három hosszú körbõl nyilt fülek ragasztásával.

Definíció: Egy kétszeresen összefüggõ gráfot minimálisnak nevezünk, ha bármely élét elhagyva elveszti kétszeres összefüggõségét.

Feladat: Bizonyítsuk be, hogy egy minimális kétszeresen összefüggõ gráf egyszerû.

Feladat: Bizonyítsuk be, hogy egy minimális kétszeresen összefüggõ gráf egyszerû.

Feladat: Bizonyítsuk be, hogy egy minimális kétszeresen összefüggõ gráfban van legalább kettõ másodfokú pont.

Feladat: Legyen G egy kétszeresen összefüggõ gráf. Bizonyítsuk be, hogy G akkor és csak akkor nem minimális, ha tartalmaz egy kört, amley két pontját a körön nem fekvõ él köt össze.

Feladat: Legyen G egy minimális kétszeresen összefüggõ gráf. Legyen C egy kör G-ben. Bizonyítsuk be, hogy C-n van 2 fokú csúcs.

Feladat: Legyen G egy minimális kétszeresen összefüggõ gráf. Legyen D a 2 fokú csúcsok halmaza. Ekkor G-D körmentes, nem összefüggõ gráf.

Feladat: Egy minimális kétszeresen összefüggõ gráfban legalább (|V|+4)/3 2 fokú csúcs van.

Feladat: Egy egyszerû minimális kétszeresen élösszefüggõ gráfban legalább (|V|+7)/4 2 fokú csúcs van.