define Eulerian graph and Hamiltonian graph.Give an example of agraph which has both Haminltonian and Eulerian circuits
Answers
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.