Bizonyítsuk be, hogy ha egy fába behúzunk egy élt, akkor pontosan egy kör keletkezik (nem több, nem kevesebb)?

Előzőnek:

Ez csak akkor működik, ha az ÖSSZES lehetséges fagráfot meg tudnánk rajzolni. De hát végtelen sok ilyen van...

Na akkor lássunk egy bizonyítás-félét:

Először is a fagráf definíciója:

Összefüggő, kört nem tartalmazó gráf.

Ebből következik, hogy bármely két pontját összeköti egy út.

(Útnak nevezzük a gráf éleinek egymáshoz csatlakozó sorozatát, amely egyetlen ponton sem megy át egynél többször.)

Ráadásul bármely két pontját pontosan egyetlen út köti össze, mert ellenkező esetben lenne kör is a gráfban.

(Ez a kulcsgondolat a bizonyításhoz.)

Na most rajzoljunk be egy újabb élt. Ennek két végpontja legyen P és Q. Ezeket összeköti egyetlen út, ami nem az új él. Az új éllel viszont keletkezett egyetlen kör, mivel P-ből Q-ba egyféleképpen eljuthatunk az eddig is létező úton, majd Q-ból P-be az új élen. Vagy fordítva akár, de ez ugyanaz a kör.

Na kb. ennyi.