2
$\begingroup$

Is it possible to have graph which is Hamiltonian and Eulerian at once with 2 bridges in it?

If yes, how can it look like?

Thank you.

Edited:

The bridge is an edge of a graph whose deletion increases its number of connected components.

Graph with one bridge - Bridge here is edge between vertices 3 and 4.

$\endgroup$
1
  • 1
    $\begingroup$ Remind me what a "bridge" means in this context? $\endgroup$ May 21, 2019 at 20:14

1 Answer 1

1
$\begingroup$

A connected graph having a bridge is not Eulerian. Let the bridge be $e$, and the connected components that result on deletion of $e$ be $C_1,C_2$. Notably, $e$ is the only edge with one end in $C_1$ and the other in $C_2$. The Euler line, if it exists, may begin at some vertex in $C_1$ and must contain $e$. When $e$ is included in the walk, we enter $C_2$. Since the Euler line must terminate at the same vertex in $C_1$, we must re-enter $C_1$. But this is not possible, as the only edge with its ends in different components is $e$, which cannot be repeated in the walk.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .