If a graph contains a bridge which is necesserily true?

329 Views Asked by At

If a graph contains a bridge which is necesserily true? 1.The graph must be a tree. 2.The graph has no Euler path 3.The graph can't contain a Hamiltonian cycle

An edge must be a bridge if it does not contain a cycle so 3?..

1

There are 1 best solutions below

1
On

A bridgeless graph is a graph without cut-edges. Hence, a graph $G$ containing a bridge contains a cut edge, say $e$. However, this definition does not have any implications on the components of $G-e$. Thus, it's possible there exists a cycle, which excludes 1, and 2.

By definition, a Hamiltonian Cycle is a spanning cycle on $G$. Since $G$ has a bridge, $G$ has a cut edge, and thus cannot be a Hamiltonian Cycle.