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
    $\begingroup$ Remind me what a "bridge" means in this context? $\endgroup$ – Thomas Andrews May 21 '19 at 20:14
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.