A PROOF OF SOME SCHOTZENBERGER-TYPE RESULTS FOR EULERIAN PATHS AND CIRCUITS ON DIGRAPHS

Internat. J. Math. & Math. Sci.

VOL. 17 NO. 3 (1994) 497-502

497

A PROOF OF SOME SCHOTZENBERGER-TYPE RESULTS FOR EULERIAN PATHS AND CIRCUITS ON DIGRAPHS

BYOUNG-SONGCHWE

Department

of Mathematics

University of Alabama Tuscaloosa, Alabama 35486

(Received December 30, 1992 and in revised form October 18, 1993)

ABSTRACT.

This papershowsthat the number ofeven Eulerianpaths equals thenulnber of Eulerianpathswhen the number ofarcsisat leasttwicethe number ofverticesofadigraph.

KEY WORDS AND PHRASES.

Digraph, Eulerian paths, odd permutation, even permutation.

1992

AMS SUBJECT CLASSIFICATION CODE.

05C30.

1.

INTRODUCTION AND CONVENTIONS.

This paper shows that in adigraph oforder nwith m arcs that satisfiesrn

_>

2n, the num- ber of even Eulerian paths equals the number of odd Eulerian paths. This result generalizes Schiitzenberger’s theorem

(see [1]

^and

[2]),

which says that in a digraph of order n with rn arcs that satisfiesm

_>

2n

+

1, the number ofeven Eulerian circuits equals the number of odd Eule- rian circuits. The proof^isalsoperhaps^moreintuitive,notdependingon toomuch terminology^or disparategraph theoryresults.

In

this paper,adigraphisdefinedbyasequence ofarcs, whereanarcisindicatedbyanordered pair suchas

(a, b),

^{andmultiplearcsand}loopsareallowed. Thoseletters which appear indescribing thearcsin the sequencedefiningthe

graph

are therefore consideredasverticesorpoints.

Note

that withthisdefinition,therecanbenoisolatedvertices. If

D

is asequence ofarcs, itslength^{is denoted} by

]DI.

^If

^VD

denotes the set of vertices which appear in

D,

^then

]VD]

denotes its cardinality.

Two

digraphs

D

^and

D

^{areconsideredtobe}the same, under appropriaterelabelingof vertices, when

D2,

as asequence ofarcs,is apermutation of the sequence ofarcswhich define

D.

^Wewrite

asequence suchas

((a,b),(c,d),(d,y)) D

in the form

D (a,b). (c,d). (d,f). For

example,the digraphwhosediagramis

a b c

o

canbeexpressedas

D1 (a,b). (b, c). (a,b)

^or

D2 (a,b). (a,b). (b, c)

^with

D1 D2

^according

toourdefinition.

Also, IO1=3

^and

IV DI

^3.

Unlike theusualway,wedefineapath of

D

as asubsequenceofapermutationof thesequence describingthe digraph

D.

Ifapath

(a,b). (a2, b2) (a,,bn)

^{is a}permutation of

D

and has the additionalproperty that

bl

^a2,

b2

a3

bn-1

an, then it is an Eulerianpath of

D.

The added conditionb, al identifiesan Eulerian circuit of

D. A path (a, b). (c, d) (e, f)

issaidto startfrom aand end at

f;

the vertex ais thestarting pointandthe vertex

f

^{isthe end}

point. Ifaand

/are paths

of

D,

then the sequenceobtained by putting

/after

^ais written providedthat the resultingsequence^isalsoa

path

of

D.

498 B. CHWE

Next, wedenote by

Ax ^D

^theset of all Eulerian paths oftire digraph

D

whichstart froxl le point^x. If the starting pointis fixedbut unimportantwe write

A

^{D. Also, vhen}

Ax ^D.

^fwe

consider as adigraph, then

A

^c

A

^D.

If and

/3

aretwo paths and ifthere are twopaths

"

^{and 3,} where eitheror both

canbeempty, such that

6

^{3, then o is apart}

^of/3

^{andve se}the notation^o

_

^{Jtoindic’ate}

thisfact.

Hence,

ifan arc

(a, b)

isaterm in ^a

path/,

wewrite

(a, b) _ ^3.

^{By/3 ismealt tile}

subsequence of/3obtainedby eliminatingall terms ofoone byone. Thus, ifarcsin/3or ct’tr

more thanonce the procedure Inay leave copies left over and the result may not be uniqtle.

notations

od(a), id(a),

^and

d(o)

aredefined ^as follows:

od(a)

i. the nulnber ofterms in

D

^wl,’h

startfrom a,

id(a)

^isthenumber of terms in

D

whichend at o, and

d(a) od(a) + ^,d(o)

^isclll,d

the degreeofa.

An

even

(odd)

pointisapoint with even

(odd) degree.

For

example,if

D

isthedigraph

D (a, o). (a, d). (c, a). (b,

a).

(b, a)

^then

^od(a)

^2,

,d(a) od(b)

2,

id(b) ^O, od(c)

1,

,d(c)

O,

od(d) O, id(d)

^{1, and}

A ^D

^{). The diagramfor}

^D

canbeconstructed as:

b ^a d

Let

abeapermutationof

D,

anddefinethe followingfunctions.

Let e()

^{if isanEulerian}

pathorcircuit, andlet

e(c)

0ifcisnot.

Let r()

^{be thesignof the}permutationo;

r(c) +

ifcisa multipleofan evennumber of transpositions, and

r(c)

^-1 ifc isamultipleofanodd number of transpositions.

Let g(c) e(c). r(c).

Whatwe arelooking^{for isa}

natural,

intuitiveproofof theformula:

Z ^g(c)

⁰

ZaeA,/ ^g(c)

^{for any x}

^VD,

if

IVD[

^nand

IDI ^_>

^{2n forallintegersn}

^_>

^1.

2.

DISCUSSION AND ARGUMENTS.

For

convenience ofnotation,wedefine

g(A D) ]-aeA.

^D

^g(c)

^{and define}

^{g(A D)}

^similarly.

If

A ^D ,

^{thennaturallywe take}

g(Aa D)

^0.

^For

^example,if

^D (a, b). (a, c). (b, a). (a, a),

withdiagram

c a b

then

A,D {(a,a)- (a,b)- (b,a). (a,c), (a,b). (b,a). (a,a). (o,c)}, AD AD ^{b, g((a,o)}

(a,b) (b,a)- (a,c))

1,

g(h,,D)

2,while

9(h,D) g(hD)

O.

For

all positiveintegers n,let

Bn

^{be the}family of digraphs

D

such that 1.

IDI ^>

^2nand

IYDI

^n,

2.

id(z) + od(x) _>

^{3for allx}

VD;

while

B$

denotesthe subfamilyofdigraphs

D

such that 1.

IDI

^{2n and}

IYDI

^n,

2.

id(x) + od(x) >

^{3forall x}

^YD.

SCHUTZENBERGER-TYPE

RESULTS FOR PATHS ^AND CIRCUITS ON DIGRAPHS ⁴⁹⁹

For

all positiveintegersn, let.4,be thefamilyofdigraphs

D

sch that 1.

IDI _

^{2n and}

^[VDI

2.

For

some q^6_

VD, zd(q)

/

od(q)

or2.

The proposition

Sn

^isthe following:

"For

j 1,...,n, if

D

^6_

mj

^U

Bj,

^then

g(A D)

^0."

In Lemma

3.1 we demonstrate that $1, 6’2, and $3 are true.

In

order to prove

Sn

in general we proceed byinductionon n, assuming

Sn-. ^In

^computing

g(A D),

^weseek toidentify

A ^D

^{with a}

union of suitable

A ^D:,

^where

^{lYD:] < ]YD,} I.

^{This is}accomplishedby identification ofalength 3 path with an arc or by deletingsome pathsin order tomaintain therelation that

g(A D)

^{0 if}

9(h O:)

^{0for alli.}

For

instance,as atrivial

example,

let

(a, v), (v, w), (w, b)

^6_

D

and

(a,v). (v,w). (w,b)

C_ for all a6_

AD. ^Let,

^{when x}

^#

^{vand x}

^#

^w,

^{D’ (D -(a,v) (v,w)} (w,b)). (a,b),

^{and let}

F

beamapof

A ^D’

^to

A ^D

^{defined by}

^{V(c) =/3(a, b)7}

^{where a}

B(a, v). (v, w). (w, b)7.

^Then

^V

is aone-to-onemapand whena,/3^6_

A ^D,/3

^{isan even}permutation ofcif and only if

F(B)

^{is an}

even permutation of

F(a).

Thus

9(A D’)

0 implies

9(A D)

^0.

In

particularweassume, basedon thisobservation, that there arenovertices vand wof

VD

forwhichthere isapathofthe type just described,whenweassumeS,_l.

In general,

ifthereare

digraphs D, D2 D

and such injeetive maps

Fi

^from

A ^Di

^to

A ^D

such that

[,JF,(A D,)

^{forms a} partition of

A ^D

^{and each}

^{9(A Di) O,}

^{then we can conclude}

g(A D)

0.

As

another exampleofan identificationofthe type described

above,

if

D

contains

(a, b)

and

(b, c)

^{and if everyc6_}

A ^D

^{startsorendswith}

(a, b). (b, c),

then take

D’ D (a, b) (b, c). In

this ease it isalsoclearthat if

9(A D’)

0, then

9(A D)

^0.

In

all ourarguments, itisthe casethat ifastatement is truefor adigraph

D,

then it isalso true forthedigraphobtainedbyreversingallares

(a, b)

^of

D

toares

(b, a).

Ifadigraph

D

^containsan are

(a, b)

with multiplicityatleast two, then trivially

9(A D)

0 sincebyasimple transposition ofone

(a, b)

withanother leaves

D unchanged

while

9(A D)

^changes

sign. Thereforeweassume nomultiplearcs.

Where

needed,

thetruthofthe proposition

S,_

is assumedinthe argumentstofollow.

PROPOSITION

1. If thereisavertexqof

D

with

d(q)

or 2, then there aredigraphs

D,, 0,1,2,...

such that

ID, >_ IDI-

^2,

IVDI ^<_ IVDI- ,

^and

g(A D.) ]i(-1)e’g(A Di),

where ei 0or1.

PROOF. Suppose D

contains ares

(t,q), (q,h),

^and

(h, bi),

1,2,3,....

Let D, (D- (t,q) -(q,h) -(h, bi)) (t, bi)

^and

]i {

^6_

A ^{D (t,q) (q,h) (h, bi) C_ a};}

^{then we see}

that

A ^Di

^{has a one to one} correspondence

Fi

^{as follows:}

Fi(a) a(t,q). (q,h). (h, bi):

^if

a

al(t, bi)a2. Clearly g(c) (-1)e’g(F,(a))

for some fixed e, 0or

,

^{for allc6_}

_A Di.

^Thus

we

get g(Ax D) (-1)e,g(Ax Di),

^whenx q andx

#

^{h. Ifx}

^h,

^{or there areno}such b,, then we canswitch and

h,

and conclude that

g(A D) ](-)’g(A D,)

if x

#

^q.

If

d(q)

2, and q is the starting point, then

AxD {(q,h)c(t,q)

c ^6_

A ^Do}

^where

Do D- (q,h) -(t,q)

andit isclear that

9(A D) =kg(AxDo).

If

d(q)

1, then

AD ^{(q,h)

^c6_

A ^D0},

^where

^{Do D-(q,h),}

^{andit isalsoclear that}

g(h D) :hg(A Do).

Alsoit isclear that

VDi

^{q and}

IDol ^_> Inl- ^2, Iunil ^<_ IVD

^1.

^Note

^that

^d(h)

ⁱⁿ

^D,

becomes smaller by 2 exceptwhen his anend point, whereitbecomessmaller by 1.

We

need this fact for the following

Lemma

1.1.

LEMMA

1.1. Whenwe assume

S,_l,

the

following

aretrue"

(A).

If

D

^6_

An,

then

g(A D)

^0.

500 B. CHWE

(B).

^If

^D

^6-

A,+I

andthereisanarc(q,b) or(h,q) in

D

such that

d(q)

2 and

d(h)

^3()r4, then

g(Ax D)

0 if x

-

^qandx

^#

^b.

PROOF. (A).

The digraphs

D,

inProposition belongto

A,-I

^U

B,-I. Hence g(A

^{D,) 0} because of

Sn-1,

and

g(A D)

0.

(B). In

Proposition 1,whcn

(q,h), (h,b,) C_ D,

if

d(h)

3or 4 in

D,

^then

d(h)

in

D,

or2, except the case in which qor h isan end point. Thus

D,

6-

A,

and

g(D,)

0. Therefore

g(Ax D) (-1),g(A D,)

0 if x

:

^{qand x}

^#

^{h. When}

^{(h,q) C_ D,}

we consider

(b,,h)

^C_

n

instead of

(h, b,);

^{then the}

argument

issinilar tothecaseof

(q, h) C_ D.

^I-I

LEMMA

1.2. Whenweassume

S,-l,

ifadigraph

D

6-

B,

hasanarc

(t, h)

^{such that an(!h} havedegree3or4, then

g(A D)

0.

PROOF.

If

h, (t,t)

C_

D,

or

(h,h)

C_

D,

then the statement reduces to a caseof

S,,_.

So

we assumethat h,

(t,t) D,

and

(h,h) D.

Accordingto our assumption, situations illustratedinthe following drawingsmay occur:

h

h

In

those diagramswecaninterchange h and

t,

and alsowecanplace thearrowsinanywaysothat

AD#.

Assuming

A ^{D #} , ()

^and

()

^{or 4, weconstruct a digraph}

^D

^6-

An+1

^from

^D

^as

follows.

D (D -(t,h)). (t,t). (t,q). (q,h)

vD VD

U

{q},

asshowninthe diagram below.

a

Let

x^6_

VD,

that is,x

V/),

andx

#

^q.

^{From Lemma 1.1.B,} g(A D)

^{0if x}

t

^h.

^On

^the

other

hand, let,

forx

t,

fl ^{c, h ^{D" (t, t). (t, q). (q, h) c_}

D (D -(t,t) -(t,q) (q,h)) (t,h)

A2 ^{{ e ]x D} (a,t) (t,t) (t, d) C_ }

D2 (D -(a,t) (t,t) -(t,d) (c,t) -(t,q) (q,h)). (a,d) (c,h)

A3 ^{{a e ]} b- (c, t). (t, t). (t, d) c

D3 (D -(c,t) (t,t) -(t,d) (a,t) -(t,q) (q,h)) (c,d) (a,h)

Then

], ]2,

^and

]3

^{form a} partition of

A/x,

^{and we see that}

g(/l) +g(hD)

by identifying

(t, t). (t, q).(q, h)

^to

(t, h),

^weseethat

g(]2) -I-g(A D2)

by identifying

(a, t).(t, t).(t, d)

SCHUTZENBERGER-TYPE ^RESULTS FOR PATHS AND CIRCUITS ON DIGRAPHS ⁵⁰¹

to

(ct, d)

^and

(c,t). (t,q).

(q.b) to

(c,h),

and we scc that

9(A3) +9(AxD3)

^by idcntifvi,g

(c,t). (t,t). (t,d)

^to

(c,d)

and

(,,t). (t,q). (q,t,)

to

(a,l,).

If

d(t)

^3and

((,,t)

isnot anarcofD, then

2 ^{{ (t,t) (t.l) }}

D2 ( -(t,t) -(t,d)

-(,

t)

-(t.q) -(q,b)).

(c, 1,)

A3 ^{{ e A, #. (,t).} (t,,). (t,#) }

D3 ( -(c,t) -(t,t) -(t,d) -(t,q) -(q, h)). (c,d)

and the resultsarcthesame.

Moreover,

itisclear that

g(A D) g(A D).

^Since

D2

^and

^D3

^donotcontain vertices and q, D2,

D3 ^A,_t

^U

^B,_.

^Th,s

g(A D2)

⁰and

9(A D3)

^0. Togetherwith

g(A, ) ^o,

^weget

g(AD)

=0, sowe get g(

A ^{D, =0for:#h. In}

^theceh=z,wecanswitcht and h. Thus

g(A, D)

0 forall z VD,or

#(A D)

0.

PROPOSITION

2.

Supposc D B

^and

A ^{D # O.}

^{Also wc sume that n 4, and that}

^D

does not contain any arcofmultiplicitymore than one, norany vertex vsuch that

d(v)

^{4 and}

arc

(,,, v) D.

Then

D

^containsan arc

(t, h)

such that

# ^h,

^{oneof and hh}

^degree

^{4and the}

otherhdegree4or3.

PROOF.

The fact that

D B

^impliesthat

vVD ^d(v)

^{4n. and}

^d(v)

^{4 forallevenpoints}

vof

D.

Since

A ^D ,

the number ofodd points^is0or2. Ifitis0, then

d(v)

4forall

thusoursertionistrue.

In

thcceof2,sayaand bareoddpoints,and

d(a) + d(b)

^{6or8. If}

d(a) + d(b)

6, then theremust be c

VD

such that

d(c)

6 and all other vertices havedegree 4,whilen 4implies thereis avertex d beside a,

b,

and c. Ifd incidentsonly^toc, then thearc

(c, d)

^or

(d, c)

^hthemultiplicitymorethan 1.

So

d must incident toaorbor apointofdegree^4.

Thusthe sertion istrue, because

d(d)

^{4 and}

d(a) d(b)

3.

In

thece

d(a) + ^d(b)

^{8, then say}

^d(a)

^{3 and}

^d(b)

^{5. Sincen 4, thereareatlettwo}

morevertices,say cand d, such that

d(c) d(d)

^4. If anyvertices ofdegree 4 do not incident toeach other and also do not incident to a then all vertices ofdegree4 must incident tob, thus

d(b)

8. This contradicts with

d(b)

5. Thus^somevertexofdegree 4h tobe incident tothe vertexa or avertexofdegree^4. Thusour sertion is true.

LEMMA

2.1. If

D B,

^{n 4, andwe sume}

^S_,

^then

g(A D)

^0.

PROOF. From

Proposition2,

D

han arc

(t, h), #

^h,such that one of and hh

degree

4 and the other h

degree

3or4. Thenby

Lemma 1.2, g(A D)

^0.

PROPOSITION

3. If

g(A D’)

0forall

D’ B,

^{then forall}

D B, g(A D)

^0whenwe

sume

S_ .

PROOF. Let D B,

a

VD,

anda

D.

Consideringadigraphtobeasequenceof arcs, it istrue that

A=

^a

Aa ^{D. Now}

^let

^VD]

^n,

^D]-

^{2n rand a}

A= ^D.

^Define

^p(a)

^{tobe the}

sequenceof the firstr termsofa, while

q(a)

to bethe subsequence ofaconsisting ofthe next2n terms. Thusa

p(a)q(a). Let Ap() ^{ A= ^{D p() p(a)} {p(a)f f Aq(a)},}

^where

i thd point

o p(),

d

() A ^o

^omj

^<

^o

⁽⁾

^U

. ⁽⁾

or

om j

< ,

^th

(A ())

^{0 b}

o S_.

f

() A

^thn

(A ())

⁰

om

Lemmn

1.1.A.If

q(a) B

^then

^{g(A q(a))}

^{0 fromour}hypothesis,

g(A D’)

0if

D’ B.

^Since

A ^{D {p(a)} A ^q(a)}

^{where arunsallelementsof}

A ^D,

^and

^g({p(a) A ^q(a)})

g(A q(a))

0, hence

g(A D)

^0.

LEMMA

3.1.

S, Se,

and $3 aretrue.

PROOF. S

^{is clearly true. If}

^D B,

^then

^D

^{is oneof}the following

(with

the orientation

arbitrary)"

502 B. CHWE

Clearly

9(A D)

^{0 in}all of the abovesituations. From

5’1

aud Proposition 3, it istrle for

B2

^as

wellasfor

A2

^fi’om

^Lemma

^{1.1. Thus $2is true.}

If

D

E

B:,

^then

^d(v)

^cangeuerate the folloving sequences whenvvariesoverelements of

(A) (3,3.6), (B) (3,4,5), (c) (4, 4,4). For

^case

(A),

^itfollows that

D

is oneof the following digral)lm

(with

the orientationarbitrary):

A

simple count yields

g(A D)

^{0 in allcases.}

^In

^case

(B),

ifthere isan arc

(t, h)

^C_

D

such that

d(t)

4 and

d(h)

3,^then

9(A D)

0 via $2 and

Lemma

1.2. Otherwise, it is thecasethatall Eulerianpaths endatthesamepathof

length

twoorstart atthesamepathoflengthtwo.

In

case

(C), 9(A D)

0 as incase

(B).

Therefore $3 follows, by Proposition3and Lemma3.1.

To

conclude, wecannowclaim:

THEOREM.

If

D

^isadigraph such that

]VD]

^nand

]D] ^_>

2n,then

9(A D)

^0; that is, the number ofevenEulerianpaths equalsthenumberof odd Eulerianpaths.

PROOF.

$1, $2,and$3aretrueby

Lemma

3.1.

For Sn,

^wheren

_>

4,we proceed by^induction on n. Whenwe assumeS,_lforn

>_

4,if

D

fi

A,,

then

9(/ D)

^0by

^Lemma

^{1.1. Alsoif}

^D

by

Lemma

2.1 and Proposition 3,

9(A D)

^{0. vI}

COROLLARY.

If

IVD

^nand

^{ID[ >}

²ⁿ

⁺

^{1, then}

9(A(,,,b)D)

^0forn 1,2,... and for all

(a, b)

C_

D,

where

A(,,,b)D ^{{a A,, D"}

^astarts with

(a, b)}.

PROOF. As

in the proofofProposition 3, let

p(a) (a, b)

while

q(a)

is the next 2n terms ofc. Then

g(A(,b)D) +g(Abq(a)).

^Since

]q(c)] >

2n and

IVq(c)] _<

n, from our theorem

g(A q(a))

0. Thus

g(A,,)D)

^0. When all points are even points, allpaths arenecessarily circuits, andthis isSchiitzenberger’stheorem, l-I

REFERENCES

1. Claude

Berge, Gr.aphs and. Hypergraphs,

Second revised edition, North-Holland, Amsterdam, 1976.

2.

R. G. Swan, An

applicationofgraph theoryto

algebra, Proc. Am.

Math.

Soc.

14

(1964),

367-373.