-
/I
.
re
/a
.
alternating
/ai
Do-ak
from
Ve
-
-90
starting
-o
k
maximal
talk
·
ak
W
=
in
fact
a
path
.
wis
①
This
②
Suppose
W
ends
at
2
.
if
the
last
edge
was
an
color
,
then
go
is
missing
at
if
the
last
edge
was
ao
color
,
then
ap
is
missing
at
2
.
Y
Consider
different
cases
based
on
·
lead
us
where
W
can
Ve
missing
as
a
,
az
CaseA
:
W
reaches
UK
Case B
:
W
reaches
Vk
=
/
Case
C
:
W
doesn't
reach
Vi
or
UK
09 Edge Coloring.pdf
N
Ve
O
W
cannot
go
to
u
before
it
goes
to
VK
.
I
because
as
is
missing
at
u)
.
the
last
edge
before
VI
has
color
a.
at
Vi
,
there
is
a
color
edge
(vi)
,
so
Wases
that
also
U
·
ak
#
VI
-
Go
Vk
=
-
ove
-
>
·
do
-
&
/a
&
ak
90
S
Go
90
-
9k
①
al
was
missing
at
Ve
,
so
it's
fire
.
②
All
internal
vertices
had
both
colors
,
so
they
are
fire
.
③
go
was
missing
at
u
,
so
it
is
fire
.
Case
B
:
W
reaches
VK-
.
Since
ak
is
missing
at
U
UK-1
,
last
edge
must
be
a
color
·
edge
.
Next
edgem
se
Vk
=
Go
but
there
is
~
Anot
it
no
/
be
al
colored
,
no
such
edge
,
ao
at
VK-
I
#New
so
W
ends
After
the
flip
,
do
has
become
free
at
VK-1
C
:
W
doesn't
reach
UK
or
VK-1
.
ur
·
non
VI
V
-
90
-
9k
T
①
It
cannot
reach
U
.
-
W
never
visits
U
,
Vi
,
VK-
Also
W
doesn't
end
at
Ve
②
The
last
Vertexz
is
none
of
EU
,
Ve
,
V
,
V
.
Class
1
&
Class
2
X(G)
=
S
X(a)
=
1
+
1
.
Equitable
Edge
Coloring
f
:
Et El
,
...,
k]
is
an
edge
coloring
of
G
.
CcCz
,
.....
C
these
are
color
classes
CiCE
that
get
color
i
.
acctof
.
-
is
equitable
keedge
coloring
if
(Icil-1(1)
1
#edge
of
Col
.
.
=
Hedges
of
col
.
4
-
U
=
No
Theorem
:
If
there
exists
a
k-edge
coloring
of
a
-
then
there
also
exists
an
quitable
k-edge
coloring
of
h.
Proof
.
Let
f
:
E
+
El
,
...,
k3
be
a
kredge
coloring
C
1,,
...
,
Ck
be
the
color
classes
.
Suppose
-
is
not
equitable
,
then
there
exist
two
color
classes
,
say
C
;
&
C
;
Ci
,
(
11
,
...,
(
:
+
2
Circ
.
=
CiUG
Ce
=
Cr
ICil
=
Kil-1
(j)
=
(j)
+
1
let
I
be
the
raph
with
idj
colored
ed,
a
=>
Max
degree
of
HE2
.
Every
conn
.
compo
of
H is-isolated
verex
,
- a
path
,
or
-
a
cycle
-
even
length
cycle
.
can
it
happen
that
all
paths
in
H
are
even
↓
length
!
!
path
compos
↑
KillCj)
+
2
.
TTJ
~
·
To
·
o
Ethere
exists
an
odd
length
path
that
starts
&
ends
with
col.i
&
alternates
idj
.
11
↓
jj
j
5. Total 14 points
This question is about a class of graphs, called degenerate graphs. First, we will see three different
definitions, and you are asked to show that they are equivalent. Then, you will be asked to show
different properties of this class of graphs.

v1
v2 v3 vi−1 vi vi+1 vj
“left degree” of vi is equal to 3

“right degree” of vi
is large vn

. . . . . .

Figure 1: An example of a 3-degeneracy ordering, where only the edges incident to vi are shown.
“Left degree” of vi

is 3. Note that “right degree” of vi can be pretty large.

(a) 5 points
Let d ≥ 1 be an integer.
Definition 1 A graph G = (V, E) is called a d-degenerate graph if, for every induced subgraph
H of G, the minimum degree of H is at most d.
Definition 2 A graph G = (V, E) is called a d-degenerate graph if, for every subgraph H of G,
the minimum degree of H is at most d.
Definition 3 A graph G = (V, E) is called a d-degenerate graph if the vertices can be ordered as
v1, v2, . . . , vn with the following property: for each 1 ≤ i ≤ n, the number of neighbors of vi to the
“left of ” vi is at most d. More formally, for each 1 ≤ i ≤ n, | {vj : {vi

, vj} ∈ E, j < i} | ≤ d. Such

an ordering is called a “d-degeneracy ordering”. See figure 1.

2

Show that the three definitions of d-degenerate graphs are equivalent to each other. That is, show
that G satisfies definition 1 iff G satisfies definition 2 iff G satisfies definition 3.
(b) 8 points
Properties of d-degenerate graphs.
(i) Let G = (V, E) be a d-degenerate graph with n vertices. Show that |E| ≤ nd.
(ii) Show that a graph of maximum degree ∆ is ∆-degenerate.
(iii) Give an example of a d-degenerate graph with maximum degree larger than d.
(iv) Give a polynomial-time algorithm to find a d-degeneracy ordering of a d-degenerate graph.
(c) 6 points
Recall the greedy coloring algorithm from the class, where in the first line we fix some arbitrary
order of vertices.
If we run the algorithm using the d-degeneracy ordering of G, then show that the algorithm
produces a (d + 1)-coloring of G.
Note that due to questions (b.ii) and (b.iii), this result generalizes what we showed in the class.