Graph G with $12$ vertices A$,$ B$,$ C$,$ D$,$ E$,$ F$,$ G$,$ H$,$ I, J$,$ K$,$ L

A $-$ B $-$ C

$|\backslash |/|$

D $-$ E $-$ F

$|/|\backslash |$

G $-$ H $-$ I

$|\backslash |/|$

J $-$ K $-$ L

Circuits displayed in the graph above

A$$B$$E$$D$$A and E$$F$$I$$H$$E$.$

Spanning Tree of the Graph

A $-$ B $-$ C

$|||$

D $-$ E F

$|||$

G H I

$|||$

J $-$ K $-$ L

Euler Circuit

Every vertex must have an even degree for a graph to have an Euler circuit.

Degrees of vertices in the graph G:

deg$($A$)=3$

deg$($B$)=4$

deg$($C$)=3$

deg$($D$)=4$

deg$($E$)=6$

deg$($F$)=4$

deg$($G$)=3$

deg$($H$)=4$

deg$($I$)=3$

deg$($J$)=3$

deg$($K$)=4$

deg$($L$)=3$

Since not all vertices have even degrees, the graph does not have an Euler circuit.

Hamiltonian Circuit

One possible Hamiltonian circuit for the graph below:

A$$B$$C$$F$$I$$H$$E$$D$$G$$J$$K$$L$$G$$A

This circuit visits each vertex exactly once before returning to the starting vertex A$.$

Do you agree with this statement why or why not?