Question

define Eulerian graph and Hamiltonian graph.Give an example of agraph which has both Haminltonian and Eulerian circuits​

Answer 1

Step-by-step explanation:

1 Eulerian and Hamiltonian Graphs.

Definition. A connected graph is called Eulerian if

it has a closed trail containing all edges of the graph.

Theorem 1 A directed multigraph G is Eulerian iff

G is connected and d

+(v) = d

−(v) for every v ∈

V (G).

L. Euler, Solution problematis as geometriam situs per-

tinentis, Commentarii Academiae Scientiarim Impe-

rialis Petropolitanae,8:128-140, 1736.

Theorem 2 A connected undirected graph is Eule-

rian iff the degree of every vertex is even.

Fleury’s Algorithm

Input: An undirected connected graph;

Output: An Eulerian trail, if it exists.

If there are vertices of odd degree, halt and return

The Graph is not Eulerian;

Else

Unmark all edges of G; choose any v ∈ V (G);

i = 0; C = ∅;

for i = 1 to |E|

{ Select unmarked edge e incident to v which in not

a bridge in the spanning subgraph comprised of

unmarked edges; if such an edge does not exist,

let e be any unmarked edge incident to v;

If e = (v, u), then C = Ceu; v = u; mark e;

}

Output C is an Eulerian trail;

3

HAMILTONIAN GRAPHS

Sir William Hamilton’s Game:

Dodecahedron

A spanning cycle is called Hamiltonian. A graph is

called Hamiltonian if it has a Hamiltonian cycle

Theorem 3 (necessary condition) If G is a Hamil-

tonian graph, then

∀S, ∅ 6= S ⊆ V (G)

the number of connected components of G − S does

not exceed |S|.

Proof. ????

Theorem 4 (sufficient condition) If G is a graph

with the smallest degree δ(G) ≥ |V (G)|/2, then G is

Hamiltonian.

Dirac’s Algorithm

Input: A connected graph G(V, E) with |V | ≥ 3 and

deg(v) ≥ |V |/2 for all v ∈ V ;

Output: A Hamiltonian cycle.

Choose any edge e = (u, v); let P = uv;

repeat {

repeat {

Renumber P as P = x1, x2, . . . , xk;

if ∃v ∈ V − P adjacent to x1 (resp. xk)

then P = vP (resp. P = P v);

else find i such that (x1, xi+1),(xi

, xk) ∈ E;

let C = (x1, xi+1, . . . , xk, xi

, xi−1, . . . x2);

}

if C is Hamiltonian, print out the output;

else

{find w ∈ V − P adjacent to a vertex in C;

form a new P containing C and w;}

Problem 1 Prove or disprove: If G is an Eulerian

graph with edges e and f that share a vertex, then G

has a closed Eulerian trail in which e and f appear

consequently?

Problem 2 What is the minimum number of trails

needed to decompose the Petersen graph? Is there a

decomposition into this number of trails using only

paths?

Problem 3 Show that Petersen graph is not Hamil-

tonian.

Problem 4 Prove that for no integer n > 0, Kn,n+1

is Hamiltonian.

Problem 5 For every integer n > 4, find a non-

Hamiltonian graph whose minimal vertex degree is

⌊

n−1

2

⌋.

Problem 6 The Hamiltonian closure of a given graph

G, denoted C(G), is the supergraph of G on V (G)

obtained by iteratively adding edges between pairs of

non-adjacent vertices whose degree sum is an least

n = |V (G)|. Prove that a simple n vertex graph G

is Hamiltonian iff C(G) is Hamiltonian.