Most grafu je taká hrana, ktorá nepatrí do žiadnej kružnice. Teda každá hrana acyklického grafu je mostom, ale most sa môže objaviť aj v grafoch obsahujúcich kružnicu. Príkladom je graf ${\displaystyle G}$ na obrázku, v ktorom sú hrany ${\displaystyle 12,23,13}$ obsiahnuté v kružnici a teda nie sú mostami. Naproti tomu hrana ${\displaystyle 34}$ nepatrí do žiadnej kružnice a teda ide o most.

Graf G

Veta

Ak z grafu vynecháme most, zväčší sa počet jeho komponentov o jednotku. Dôkaz vety vyplýva priamo z definície mostu. Most hrá medzi hranami podobnú úlohu ako artikulácia medzi vrcholmi.

Literatúra

• Znám, Š: Kombinatorika a teória grafov. Bratislava, Matematicko-fyzikálna fakulta Univerzity Komenského. 1982, s. 42