Eulerian Graph

Definitions : A (directed) trail that traverses every edge and every vertex of Gis
called anEuler(directed)trail. A closed Euler (directed) trail is called
anEuler(directed)circuit. A (di)graph is eulerian if it contains an Euler
(directed)circuit, andnoneulerianotherwise.
Euler trails and Euler circuits are named after L. Euler (1707–1783), who in
1736characterized those graphs which contain them in the earliest known paper on
graphtheory. The well-known K ̈onigsberg seven bridges problem is as follows.
Euler abstracted the K ̈onigsberg seven bridges as the graphshown in Figure 1.20
(b),where vertices represent the four lands and edges representthe seven bridges,
for-malized the K ̈onigsberg seven bridges problem to the question whether such a
graphcontains an Euler circuit.
Euler abstracted the K ̈onigsberg seven bridges as the graphshown in Figure 1.20
(b), where vertices represent the four lands and edges representthe seven bridges,
for-malized the K ̈onigsberg seven bridges problem to the question whether such a
graphcontains an Euler circuit.

Characteristic Theorem: We now give a characterization of euleriangraphs.

Theorem 1.7 A digraph is eulerian if and only if it is connectedand balanced.

Proof: Suppose thatGis an Euler digraph and letCbe an Euler directed circuit of G.
Then G is connected sinceCtraverses every vertex of G by the definition.
Arbitrarily choosex∈V(C). It each time occurs as an internal vertex of C, two edges
are incident with x, one out-going edge and another in-coming edge. Thus, d +G(x)
=d−G(x).
Conversely, suppose to the contrary that a connected and balanced digraph is not
eulerian. Choose such a digraph with the number of edges as few as possible. Then
G contains directed cycle since δ+=δ−6= 0 (the exercise 1.7.3). Let C be a directed
circuit of maximum length in G. By our assumption, C is not an Euler directed
circuit of G, and so G−E(C) contains a connected component G′ with
(G′)>0. Since C is itself balanced, thus the connected graph D′ is also balanced.
Since ε(G′)< ε(G), it follows from the choice of Gt hat G′ contains an Euler
directedcircuitC′. SinceGis connected,V(C)∩V(C′)6=∅. Thus, C ⊕ C′ is a
directedcircuit ofGwith length larger than ε(C), contradicting the choice of C.
Applications: We conclude this section with two important classes of eulerian
digraphs, the de Bruijn digraphs and the Kautz digraphs, which occur in the litera-
ture and textbooks of graph theory frequently.
Example 1.8.1 For any integersdandnwithn≥1 andd≥2, we have,in Example
1.4.4, defined then-dimensionald-aryde Bruijn digraphB(d,n) as(n−1)th iterated
line digraphLn−1(K+d), whereK+ddenotes the digraph obtained from a complete
digraphKdof orderdby appending one loop at each vertex. We have known that it is
ad-regular connected digraph and so an eulerian digraph by Theorem 1.7.We here
give another equivalent definition of de Bruijn digraphB(d,n). Itsvertex-
setV={x1x2···xn:xi∈{0,1,···,d−1}, i= 1,2,···,n},and edge-setE, where forx,y∈V,
ifx=x1x2···xn, then(x,y)∈E⇐⇒y=x2x3···xnα, α∈{0,1,···,d−1}.Three smaller de
Bruijn digraphsB(2,n) are depicted in Figure 1.21 according to this kind of
definition.
Example 1.8.3 For any given integersdandnwithn≥1 andd≥2,we have, also in
Example 1.4.4, defined then-dimensional d-ary Kautz digraph K(d,n) as (n−1)th
iterated line digraphLn−1(Kd+1), whereKd+1is a complete
GRAPH

An Eulerian graph is a graph containing an Eulerian cycle. The numbers of Eulerian graphs with ,
2, ... nodes are 1, 1, 2, 3, 7, 15, 52, 236, ... (OEIS A133736), the first few of which are illustrated above
The corresponding numbers of connected Eulerian graphs are 1, 0, 1, 1, 4, 8, 37, 184, 1782, ... (OEIS
A003049; Robinson 1969; Liskovec 1972; Harary and Palmer 1973, p. 117), the first few of which are
illustrated above.
Some care is needed in interpreting the term, however, since some authors define an Euler graph as a
different object, namely a graph for which all vertices are of even degree (motivated by the following
theorem). Euler showed (without proof) that a connected simple graph is Eulerian iff it has no graph
vertices of odd degree (i.e., all vertices are of even degree). While the number of connected Euler graphs
on nodes is equal to the number of connected Eulerian graphs on nodes, the counts are different for
disconnected graphs since there exist disconnected graphs having multiple disjoint cycles with each node
even but for which no single cycle passes through all edges.
A directed graph is Eulerian iff every graph vertex has equal indegree and outdegree. A planar bipartite
graph is dual to a planar Eulerian graph and vice versa. The numbers of Eulerian digraphs on , 2, ...
nodes are 1, 1, 3, 12, 90, 2162, ... (OEIS A058337).

Finding the largest subgraph of graph having an odd number of vertices which is Eulerian is an NP-
complete problem (Skiena 1990, p. 194). A graph can be tested in the Wolfram Language to see if it
Eulerian using the command EulerianGraphQ[g].

The following table gives some named Eulerian graphs.

 graph
singleton graph 1
triangle graph 3
square graph 4
pentatope graph 5
octahedral graph 6
16-cell graph 8
cuboctahedral graph 12
Chvátal graph 12
tesseract graph 16
Hoffman graph 16
Robertson graph 19
Folkman graph 20
24-cell graph 24
small rhombicuboctahedral graph 24
25-Grünbaum graph 25
Doyle graph 27
icosidodecahedral graph 30
Harborth graph 52
Gewirtz graph 56
small rhombicosidodecahedral graph 60
Meredith graph 70
600-cell graph 120
McLaughlin graph 275
120-cell graph 600

Eulerian Digraphs
The concept of digraphs (or directed graphs) is one of the richest theories in graph
theory, mainly because of their applications to physical problems. For example,
flow network s with valves in the pipes and electrical networks are represented by
digraphs. They are applied in abstract representations of computer programs and
are an invaluable tools in the study of sequential machines. They are also used for
systems analysis in control theory. Most of the concepts and terminology of
undirected graphs are also applicable to digraphs ,and hence in this chapter more
emphasis will be given to those properties of digraphs that are not found in
undirected graphs. There are two different treatments of digraphs—one can be
found in the book by Ha r-ray, Norman and Cartwright and the other in the book
by Berge. The for merd is cusses the application of digraphs to sociological
problems, and the latter gives a com- prehensive mathematical treatment. One can
also refer to the books by N. Deo, Harary, Behzad, Chartrand and Lesniak-Foster,
and Buckley and Harary.

Basic Definitions
Digraphs (Directed graphs) :A digraph Dis a pair (V,A), where Vis a nonempty
set whose elements are called the vertices and A is the subset of the set of ordered
pairs of distinct elements of V. The elements of are called the arcs of D(Fig.
11.1(a)).

Multi digraphs : A multi digraph Dis a pair (V,A), where Vis a nonempty set of
vertices and A is a multiset of arcs, which is a multi sub set of the set of ordered
pairs of distinct elements of V. The number of times an arc occurs in Dis called its
multiplicity and arcs with multiplicity greater than one are called multiple arcs of
D (Fig. 11.1(b)).

General digraphs :A general digraph Dis a pair (V,A), where V is a nonempty set
of vertices, and A is a multiset of arcs, which is a multi sub set of the cartesian
product of V with itself. An arc of the for mu u is called a loop of D and arcs
which are not loops are called proper arcs of D. The number of times an arc occurs
is called its multiplicity. A loop with multiplicity greater than one is called a
multiple loop (Fig. 11.1(c).

Oriented graph: A digraph containing no symmetric pair of arcs is called an

oriented graph (Fig. 11.1(d)).

For u,v ∈V, an arca= (u ,v)∈A is denoted by uv and implies that a is directed from
u to v. Here ,u is the initial vertex (tail) and vis the terminal vertex (head). Also we
say that a joins u t o v; a is incident with u and v; a is incident from u and a is
incident tov; and u is adjacent to v and vis adjacent from u. In case both u v and v u
be long to A, then u v and vu are called asymmetric pair of arcs. For an y v ∈V, the
number of arcs incident to vis the in degree of v and is denoted by d−(v). The
number of arcs incident from vis called the out degree of v and is denoted by d+
(v). Berge calls in degree and out degree a sinner and outer-demi degrees. The total
degree(or simply degree) of v is d(v) =d−(v) +d+(v).
We define N+(v)and N−(v)by
N+(v) ={u ∈V : vu ∈A}and N−(v) ={u ∈ V:uv∈A}
If d(v) = k for every v ∈ V, then Dis said to be a k – regular digraph. If for every
v ∈ V ,d−(v) =d+(v), the digraph is said to be an is graph or a balanced digraph.
We note that an is o graph is an even degree digraph, but not necessarily regular.
Also, every symmetric digraph is an is o graph. Edmonds and Johnson [70] call
isographs as asymmetric digraphs and Berge [23]calls them pseudo-symmetric
graphs. K o t zig [137, 138] calls an anti-symmetric is o graph as oriented-in-
equilibrium or a ρ-graph.
A vertex for which d+(v) =d−(v) =0is called an is o late. A vertex is called a
trans - mitteror are ceiver according as d+(v)>0,d−(v)= 0 or d + (v) =0,d−(v)>0. A
vertex is called a carrier if d+(v) =d−(v) =1.
Underlying graph of a digraph : Let D= (V,A)be a digraph. The graph G=
(V,E),where uv ∈ E if and only If uv or vu or both are in A, is called the underlying
graph of D. This is also called the covering graph C(D) of D. Here we denote C(D)
by G(D)or simply by G.
In case G = (V,E) is a graph, the digraph with vertex set V and a symmetric uv
whenever uv ∈ E, is called the digraph corresponding to G, and is denoted by D
(G), or D. Clearly, D (G) is a symmetric digraph. An oriented graph obtained from
the graph G= (V,E) by replacing each edge uv ∈ E by an arc uv or vu, but not both
is called an orientation of G and is denoted by O (G) or O
Complete symmetric digraph: A digraph D = (V,A) is said to be complete if both
uv and vu ∈ A, for all u, v ∈ V. Obviously this corresponds to Kn, where |V|= n,
and is denoted by K∗n. A complete antisymmetric digraph, or a complete oriented
graph is called a tournament. Clearly, a tournament is an orientation of Kn