„Fa (gráfelmélet)” változatai közötti eltérés

A [[gráfelmélet]]ben a '''fának''' vagy '''fagráfnak''' nevezzük azokat a [[gráf]]okat, amelynek bármely két csúcsát ''pontosan egy'' út köti össze, azaz a fák körmentes [[Gráfelmélet#Összefüggőség|összefüggő]] gráfok. '''Erdőnek''' nevezzük azokat gráfokat, amelynek bármely két csúcsát ''legfeljebb egy'' út köti össze, azaz ahogy az elnevezés is utal rá, az erdő összeolyan nemgráf, függőaminek fákkomponensei uniójafák, vagy ami ezzel ekvivalens, az erdők körmentes gráfok.

* Minden összefüggő G gráfnak van feszítő fája, azaz létezik hozzá olyan fa, ami tartalmazza a G összes csúcspontját, és amelynek élei egyben a G gráfnak is élei,. illetveTovábbá minden gráfnak van feszítő erdője, tehát létezik hozzá olyan erdő, aminek a komponensei azonosak az eredeti gráféival.<ref>Ennek az állításnak a [[számosság|végtelen]] gráfokra való igazolása felhasználja a [[kiválasztási axióma|kiválasztási axiómá]]t.</ref>

* Minden fának, amelynek van legalább egykét csúcspontja, van legalább egykét levele, azaz van legalább egykét olyan csúcsa, amelynek a [[fokszám (gráfelmélet)|fokszám]]a 1.