graph-theory_fundametal_concepts_chap.ppt

the chapter contains fundamental concepts of graph theory

1. Graph Theory
Ch. 1. Fundamental Concept
1
Chapter 1
Fundamental Concept
1.1 What Is a Graph?
1.2 Paths, Cycles, and Trails
1.3 Vertex Degree and Counting
1.4 Directed Graphs

2. Graph Theory
Ch. 1. Fundamental Concept
2
The KÖnigsberg Bridge Problem
Königsber is a city on the Pregel river in Prussia
The city occupied two islands plus areas on both
banks
Problem:
Whether they could leave home, cross every bridge
exactly once, and return home.
X
Y
Z
W

3. Graph Theory
Ch. 1. Fundamental Concept
3
A Model
A vertex: a region
An edge: a path(bridge) between two regions
e
1
e
2
e
3
e
4
e
6
e
5
e
7
Z
Y
X
W
X
Y
Z
W

4. Graph Theory
Ch. 1. Fundamental Concept
4
What Is a Graph?
A graph G is a triple consisting of:
–A vertex set V(G)
–An edge set E(G)
–A relation between an edge and a pair of vertices
e
1
e
2
e
3
e
4
e
6
e
5
e
7
Z
Y
X
W

5. Graph Theory
Ch. 1. Fundamental Concept
5
Loop, Multiple edges
Loop: An edge whose endpoints are equal
Multiple edges: Edges have the same pair of
endpoints
loop
Multiple
edges

6. Graph Theory
Ch. 1. Fundamental Concept
6
Simple Graph
Simple graph: A graph has no loops or multiple
edges
loop
Multiple
edges
It is not simple. It is a simple graph.

7. Graph Theory
Ch. 1. Fundamental Concept
7
Adjacent, neighbors
Two vertices are adjacent and are neighbors if
they are the endpoints of an edge.
Example:
–A and B are adjacent.
–A and D are not adjacent.
A B
C D

8. Graph Theory
Ch. 1. Fundamental Concept
8
Finite Graph, Null Graph
Finite graph: an graph whose vertex set and edge
set are finite.
Null graph: the graph whose vertex set and edges
are empty.

9. Graph Theory
Ch. 1. Fundamental Concept
9
Complement
Complement of G: The complement G’ of a
simple graph G :
–A simple graph
–V(G’) = V(G)
–E(G’) = { uv | uv E(G) }
G
u
v
w
x
y
G’
u
v
wx
y

10. Graph Theory
Ch. 1. Fundamental Concept
10
Clique and Independent set
A Clique in a graph: a set of pairwise adjacent
vertices (a complete subgraph)
An independent set in a graph: a set of pairwise
nonadjacent vertices.
Example:
–{x, y, u} is a clique in G.
–{u, w} is an independent set. G
u
v
w
x
y

11. Graph Theory
Ch. 1. Fundamental Concept
11
Bipartite Graphs
A graph G is bipartite if V(G) is the union of two
disjoint independent sets called partite sets of G
Also: The vertices can be partitioned into two sets
such that each set is independent
Matching Problem
Job Assignment Problem
Workers
Jobs
Boys
Girls

12. Graph Theory
Ch. 1. Fundamental Concept
12
Chromatic Number
The chromatic number of a graph G, written x(G), is
the minimum number of colors needed to label the
vertices so that adjacent vertices receive different
colors
Red
Green
Blue
Blue
x(G) = 3

13. Graph Theory
Ch. 1. Fundamental Concept
13
Maps and coloring
A map is a partition of the plane into connected
regions
Can we color the regions of every map using at
most four colors so that neighboring regions have
different colors?
Map Coloring  graph coloring
–A region  A vertex
–Adjacency  An edge

14. Graph Theory
Ch. 1. Fundamental Concept
14
Scheduling and graph Coloring 1
Two committees can not hold meetings at the same
time if two committees have common member
common
member
Committee 1 Committee 2

15. Graph Theory
Ch. 1. Fundamental Concept
15
Scheduling and graph Coloring 1
Model:
–One committee being represented by a vertex
–An edge between two vertices if two
corresponding committees have common member
–Two adjacent vertices can not receive the same
color
common
member
Committee 1 Committee 2

16. Graph Theory
Ch. 1. Fundamental Concept
16
Scheduling and graph Coloring 2
Scheduling problem is equivalent to graph
coloring problem.
common
memberCommittee 1
Committee 2
Committee 3
Common Member
Different Color
No Common Member
Same Color OK
Same time slot OK

17. Graph Theory
Ch. 1. Fundamental Concept
17
Path and Cycle
Path: a sequence of distinct vertices such that two
consecutive vertices are adjacent.
–Example: (a, d, c, b, e) is a path
–(a, b, e, d, c, b, e, d) is not a path; it is a walk.
Cycle: a closed Path
–Example: (a, d, c, b, e, a) is a cycle
a b
c
d
e

18. Graph Theory
Ch. 1. Fundamental Concept
18
Subgraphs
A subgraph of a graph G is a graph H such that:
–V(H)  V(G) and E(H)  E(G) and
–The assignment of endpoints to edges in H is the
same as in G.

19. Graph Theory
Ch. 1. Fundamental Concept
19
Subgraphs
Example: H
1, H
2, and H
3 are subgraphs of G
c
d
a b
d
e
a
b
c
de
H
1
G
H
3
H
2
a b
c
d
e

20. Graph Theory
Ch. 1. Fundamental Concept
20
Connected and Disconnected
Connected: There exists at least one path between
two vertices.
Disconnected: Otherwise
Example:
–H
1 and H
2 are connected.
–H
3 is disconnected.
c
d
a
b
d
e
a b
c
de
H
1
H
3H
2

21. Graph Theory
Ch. 1. Fundamental Concept
21
Adjacency, Incidence, and Degree
Assume e
i is an edge whose endpoints are (v
j,v
k)
The vertices v
j and v
k are said to be adjacent.
The edge e
i is said to be incident upon v
j
Degree of a vertex v
k
is the number of edges incident upon v
k
.
It is denoted as d(v
k)
e
i
v
j
v
k

22. Graph Theory
Ch. 1. Fundamental Concept
22
Adjacency matrix
Let G = (V, E), |V| = n and |E|=m
The adjacency matrix of G written A(G), is the n-
by-n matrix in which entry a
i,j is the number of
edges in G with endpoints {v
i, v
j}.
a
b
c
d
e
w
x
y z
w x y z
0 1 1 0
1 0 2 0
1 2 0 1
0 0 1 0
w
x
y
z

23. Graph Theory
Ch. 1. Fundamental Concept
23
Incidence Matrix
Let G = (V, E), |V| = n and |E|=m
The incidence matrix M(G) is the n-by-m matrix in which
entry m
i,j is 1 if v
i is an endpoint of e
i and otherwise is 0.
a
b
c
d
e
w
x
y
z
a b c d e
1 1 0 0 0
1 0 1 1 0
0 1 1 1 1
0 0 0 0 1
w
x
y
z

24. Graph Theory
Ch. 1. Fundamental Concept
24
Isomorphism
An isomorphism from a simple graph G to a simple
graph H is a bijection f:V(G)V(H) such that uv
E(G) if and only if f(u)f(v)  E(H)
–We say “G is isomorphic to H”, written G  H
H
G
w
x z
y c d
ba
f
1: w x y z
c b d a
f
2: w x y z
a d b c

25. Graph Theory
Ch. 1. Fundamental Concept
25
Complete Graph,
Complete Bipartite Graph or Biclique
Complete Graph: a simple graph whose vertices are
pairwise adjacent.
Complete bipartite graph (biclique) is a simple bipartite
graph such that two vertices are adjacent if and only if
they are in different partite sets.
Complete Graph Complete Bipartite Graph

26. Graph Theory
Ch. 1. Fundamental Concept
26
Petersen Graph 1.1.36
The petersen graph is the simple graph whose vertices
are the 2-element subsets of a 5-element set and whose
edges are pairs of disjoint 2-element subsets

27. Graph Theory
Ch. 1. Fundamental Concept
27
Petersen Graph 1.1.37
 Assume: the set of 5-element be (1, 2, 3, 4, 5)
–Then, 2-element subsets:
(1,2) (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5)
Disjoint, so
connected
45: (4, 5)
12
34
15
23
45
35
13
14
24
25

28. Graph Theory
Ch. 1. Fundamental Concept
28
Petersen Graph 1.1.36
Three drawings

29. Graph Theory
Ch. 1. Fundamental Concept
29
Theorem: If two vertices are non-adjacent in the
Petersen Graph, then they have exactly one common
neighbor. 1.1.38
Proof:
x, zx, y
No connection,
Joint, One common element.
u, vSince 5 elements totally,
5-3 elements left.
Hence, exactly one of this
kind.
3 elements in these vertices totally

30. Graph Theory
Ch. 1. Fundamental Concept
30
Girth 1.1.39, 1.1.40
Girth: the length of its shortest cycle.
–If no cycles, girth is infinite

31. Graph Theory
Ch. 1. Fundamental Concept
31
Girth and Petersen graph 1.1.39, 1.1.40
Theorem: The Petersen Graph has girth 5.
Proof:
–Simple  no loop  no 1-cycle (cycle of length 1)
–Simple  no multiple  no 2-cycle
–5 elements no three pair-disjoint 2-sets no 3-
cycle
–By previous theorem, two nonadjacent vertices has
exactly one common neighbor no 4-cycle
–12-34-51-23-45-12 is a 5-cycle.

32. Graph Theory
Ch. 1. Fundamental Concept
32
Walks, Trails1.2.2
A walk: a list of vertices and edges v
0, e
1, v
1, …., e
k
,
v
k such that, for 1ik, the edge e
i has endpoints v
i-
1 and v
i.
A trail : a walk with no repeated edge.

33. Graph Theory
Ch. 1. Fundamental Concept
33
Paths 1.2.2
A u,v-walk or u,v-trail has first vertex u and last
vertex v; these are its endpoints.
A u,v-path: a u,v-trail with no repeated vertex.
The length of a walk, trail, path, or cycle is its
number of edges.
A walk or trail is closed if its endpoints are the same.

34. Graph Theory
Ch. 1. Fundamental Concept
34
Lemma: Every u,v-walk contains a u,v-path 1.2.5
Proof:
Use induction on the length l of a u, v-walk W.
Basis step: l = 0.
–Having no edge, W consists of a single vertex
(u=v).
–This vertex is a u,v-path of length 0.
to be continued

35. Graph Theory
Ch. 1. Fundamental Concept
35
Lemma: Every u,v-walk contains a u,v-path 1.2.5
Proof: Continue
Induction step : l  1. (see the figure in the next page)
–Suppose that the claim holds for walks of length
less than l.
–If W has no repeated vertex, then its vertices and
edges form a u,v-path.
–If W has a repeated vertex w, then deleting the
edges and vertices between appearances of w
(leaving one copy of w) yields a shorter u,v-walk
W’ contained in W. (see next page)
–By the induction hypothesis, W ’ contains a u,v-
path P,and this path P is contained in W.

36. Graph Theory
Ch. 1. Fundamental Concept
36
Lemma: Every u,v-walk contains a u,v-path 1.2.5
An example:
u
v
W
P
Delete

37. Graph Theory
Ch. 1. Fundamental Concept
37
Components 1.2.8
The components of a graph G are its maximal
connected subgraphs.
A component (or graph) is trivial if it has no edges;
otherwise it is nontrivial.
An isolated vertex is a vertex of degree 0.
r
q
suv w
t
p x
y z

38. Graph Theory
Ch. 1. Fundamental Concept
38
Proof:
–An n-vertex graph with no edges has n
components
–Each edge added reduces this by at most 1
–If k edges are added, then the number of
components is at least n-k
Theorem: Every graph with n vertices and k edges
has at least n-k components 1.2.11

39. Graph Theory
Ch. 1. Fundamental Concept
39
Theorem: Every graph with n vertices and k edges
has at least n-k components 1.2.11
Examples:
n=2, k=1,
1 component
n=3, k=2,
1 component
n=6, k=3,
3 components
n=6, k=3,
4 components

40. Graph Theory
Ch. 1. Fundamental Concept
40
Cut-edge, Cut-vertex 1.2.12
A cut-edge or cut-vertex of a graph is an edge or
vertex whose deletion increases the number of
components.
Not a Cut-vertex
Cut-edge
Cut-edge
Cut-vertex

41. Graph Theory
Ch. 1. Fundamental Concept
41
Cut-edge, Cut-vertex 1.2.12
G-e or G-M : The subgraph obtained by deleting
an edge e or set of edges M.
G-v or G-S : The subgraph obtained by deleting a
vertex v or set of vertices S.
e
G-eG

42. Graph Theory
Ch. 1. Fundamental Concept
42
Induced subgraph 1.2.12
An induced subgraph:
–A subgraph obtained by deleting a set of vertices.
–We write G[T] for G- T’, where T’ =V(G)-T;
–G[T] is the subgraph of G induced by T.
Example:
–Assume T:{A, B, C, D}
B
A
C D
E
B
A
C D
G[T]
G

43. Graph Theory
Ch. 1. Fundamental Concept
43
Induced subgraph 1.2.12
More Examples:
–G
2 is the subgraph of G
1 induced by (A, B, C, D)
–G
3 is the subgraph of G
1 induced by (B, C)
–G
4 is not the subgraph induced by (A, B, C, D)
B
A
C D
E
B
A
C D
B
C
B
A
C D
G
1 G
2
G3 G
4

44. Graph Theory
Ch. 1. Fundamental Concept
44
Induced subgraph 1.2.12
A set S of vertices is an independent set if and only
if the subgraph induced by it has no edges.
–G
3 is an example.
B
A
C D
E
B
C
G
1
G3

45. Graph Theory
Ch. 1. Fundamental Concept
45
Theorem: An edge e is a cut-edge if and only if e
belongs to no cycles. 1.2.14
Proof :1/2
Let e= (x, y) be an edge in a graph G and H be the
component containing e.
–Since deletion of e effects no other component, it
suffices to prove that H-e is connected if and only if
e belongs to a cycle.
First suppose that H-e is connected.
–This implies that H-e contains an x, y-path,
–This path completes a cycle with e.

46. Graph Theory
Ch. 1. Fundamental Concept
46
Theorem: An edge e is a cut-edge if and only if e
belongs to no cycles. 1.2.14
Proof :2/2
Now suppose that e lies in a cycle C.
–Choose u, vV(H)
•Since H is connected, H has a u, v-path P.
–If P does not contain e
• Then P exists in H-e
–Otherwise
•Suppose by symmetry that x is between u and y on P
•Since H-e contains a u, x-path along P,
the transitivity of the connection relation implies that
H-e has a u, v-path.
–We did this for all u, v  V(H), so H-e is connected.

47. Graph Theory
Ch. 1. Fundamental Concept
47
Theorem: An edge e is a cut-edge if and only
if e belongs to no cycles. 1.2.14
An Example:
u
x y
e
P
C
v

48. Graph Theory
Ch. 1. Fundamental Concept
48
Lemma: Every closed odd walk contains an odd cycle
Proof:1/2
Use induction on the length l of a closed odd walk W.
l=1. A closed walk of length 1 traverses a cycle of
length 1.
We need to prove the claim holds if it holds for closed
odd walks shorter than W.

49. Graph Theory
Ch. 1. Fundamental Concept
49
Lemma: Every closed odd walk contains an odd cycle
Proof: 2/2
Suppose that the claim holds for closed odd walks shorter than
W.
–If W has no repeated vertex (other than first = last),
then W itself forms a cycle of odd length.
–Otherwise,
•Need to prove: If repeated, W includes a shorter
closed odd walk. By induction, the theorem hold
•If W has a repeated vertex v, then we view W as
starting at v and break W into two v,v-walks.
•Since W has odd length, one of these is odd and the
other is even. (see the next page)
•The odd one is shorter than W, by induction
hypothesis, it contains an odd cycle, and this cycle
appears in order in W.

50. Graph Theory
Ch. 1. Fundamental Concept
50
Lemma: Every closed odd walk contains an odd
cycle 1.2.15
Even
v
Odd
Odd = Odd + Even

51. Graph Theory
Ch. 1. Fundamental Concept
51
Theorem: A graph is bipartite if and only if it has
no odd cycle. 1.2.18
Examples:
B
A
D C
A
C
B
D
A
C
B
D
F
E
A
C
B
D
E F

52. Graph Theory
Ch. 1. Fundamental Concept
52
Theorem: A graph is bipartite if it has no odd cycle. 1.2.18
Proof: (sufficiency1/3)
Let G be a graph with no odd cycle.
We prove that G is bipartite by constructing a bipartition of each nontrivial
component H.
For each v  V(H), let f(v) be the minimum length of a u, v-path. Since H is
connected, f(v) is defined for each v  V(H) .
u
v
'v
( ')f v
( )f v

53. Graph Theory
Ch. 1. Fundamental Concept
53
Theorem: A graph is bipartite if it has no odd cycle. 1.2.18
Proof: (sufficiency2/3)
Let X={v  V(H): f(v) is even} and Y={v  V(H): f(v) is
odd}
An edge v,v’ within X (or Y) would create a closed odd walk
using a shortest u, v-path, the edge v, v’ within X (or Y) and
the reverse of a shortest u, v’-path.
u
v
'v
A closed odd walk using
1)a shortest u, v-path,
2)the edge v, v’ within X (or Y) , and
3)the reverse of a shortest u, v’-
path.

54. Graph Theory
Ch. 1. Fundamental Concept
54
Theorem: A graph is bipartite if it has no odd cycle. 1.2.18
Proof: (sufficiency3/3)
By Lemma 1.2.15, such a walk must contain an odd cycle,
which contradicts our hypothesis
Hence X and Y are independent sets. Also XY = V(H), so H is
an X, Y-bipartite graph
u
v
'v
Even (or Odd)
Even (or Odd)
Odd Cycle
Because:
even (or odd) + even (or odd) = even
even + 1 = odd
Since no odd cycles, vv’ doesn’t
exist.
We have:
X and Y are independent sets

55. Graph Theory
Ch. 1. Fundamental Concept
55
Theorem: A graph is bipartite only if it has no
odd cycle. 1.2.18
Proof: (necessity)
Let G be a bipartite graph.
Every walk alternates between the two sets of a
bipartition
So every return to the original partite set happens
after an even number of steps
Hence G has no odd cycle

56. Graph Theory
Ch. 1. Fundamental Concept
56
Eulerian Circuits 1.2.24
A graph is Eulerian if it has a closed trail containing
all edges.
We call a closed trail a circuit when we do not specify
the first vertex but keep the list in cyclic order.
An Eulerian circuit or Eulerian trail in a graph is a
circuit or trail containing all the edges.

57. Graph Theory
Ch. 1. Fundamental Concept
57
Even Graph, Even Vertex, and Maximal Path1.2.24
An even graph is a graph with vertex degrees all
even.
A vertex is odd [even] when its degree is odd
[even].
A maximal path in a graph G is a path P in G that
is not contained in a longer path.
–When a graph is finite, no path can extend forever
, so maximal (non-extendible) paths exist.

58. Graph Theory
Ch. 1. Fundamental Concept
58
Lemma: If every vertex of graph G has degree at
least 2, then G contains a cycle. 1.2.25
Proof:
Let P be a maximal path in G, and let u be an endpoint of P
Since P cannot be extended, every neighbor of u must already be
a vertex of P
Since u has degree at least 2, it has a neighbor v in V(P) via an
edge not in P
The edge uv completes a cycle with the portion of P from v to u
u
P
Impossible
v
P
u
Must

59. Graph Theory
Ch. 1. Fundamental Concept
59
Theorem: A graph G is Eulerian if and only if it has at most
one nontrivial component and its vertices all have even
degree. 1.2.26
Proof: (Necessity)
Suppose that G has an Eulerian circuit C.
Each passage of C through a vertex uses two
incident edges, and the first edge is paired with the
last at the first vertex.
Hence every vertex has even degree. Also, two
edges can be in the same trail only when they lie in
the same component, so there is at most one
nontrivial component.

60. Graph Theory
Ch. 1. Fundamental Concept
60
Theorem: A graph G is Eulerian if and only if it has at most one
nontrivial component and its vertices all have even degree.1.2.26
Proof: (Sufficiency 1/3)
Assuming that the condition holds, we obtain an
Eulerian circuit using induction on the number of
edges, m.
Basis step: m=0. A closed trail consisting of one
vertex suffices. →

61. Graph Theory
Ch. 1. Fundamental Concept
61
Theorem: A graph G is Eulerian if and only if it has at most one
nontrivial component and its vertices all have even degree. 1.2.26
Proof: (Sufficiency 2/3)
Induction step: m>0.
–When even degrees, each vertex in the nontrivial
component of G has degree at least 2.
–By Lemma 1.2.25, the nontrivial component has a cycle
C.
– Let G’ be the graph obtained from G by deleting E(C).
–Since C has 0 or 2 edges at each vertex, each component of
G’ is also an even graph.
–Since each component is also connected and has fewer than
m edges, we can apply the induction hypothesis to conclude
that each component of G’ has an Eulerian circuit. →

62. Graph Theory
Ch. 1. Fundamental Concept
62
Theorem: A graph G is Eulerian if and only if it has at most one
nontrivial component and its vertices all have even degree. 1.2.26
Proof: (Sufficiency 3/3)
Induction step: m>0. (continued)
–To combine these into an Eulerian circuit of G, we
traverse C, but when a component of G’ is entered
for the first time we detour along an Eulerian
circuit of that component.
–This circuit ends at the vertex where we began the
detour. When we complete the traversal of C, we
have completed an Eulerian circuit of G.

63. Graph Theory
Ch. 1. Fundamental Concept
63
Proposition: Every even graph decomposes into cycles1.2.27
Proof:
In the proof of Theorem 1.2.26
–It is noted that every even nontrivial graph has a
cycle
–The deletion of a cycle leaves an even graph
Thus this proposition follows by induction on the
number of edges

64. Graph Theory
Ch. 1. Fundamental Concept
64
Proposition: If G is a simple graph in which every vertex has
degree at least k, then G contains a path of length at least k.
If k2, then G also contains a cycle of length at least k+1.
1.2.28
Proof: (1/2)
Let u be an endpoint of a maximal path P in G.
Since P does not extend, every neighbor of u is in
V(P).
Since u has at least k neighbors and G is simple, P
therefore has at least k vertices other than u and has
length at least k.

65. Graph Theory
Ch. 1. Fundamental Concept
65
Proposition: If G is a simple graph in which every vertex has
degree at least k, then G contains a path of length at least k.
If k2, then G also contains a cycle of length at least k+1.
1.2.28
Proof: (2/2)
If k  2, then the edge from u to its farthest
neighbor v along P completes a sufficiently long
cycle with the portion of P from v to u.
u
v
d(u)  k
At least k+1 vertices
Length  k

66. Graph Theory
Ch. 1. Fundamental Concept
66
Degree1.3.1
The degree of vertex v in a graph G, written or d(v), is
the number of edges incident to v, except that each loop at v
counts twice
The maximal degree is (G)
The minimum degree is  (G)
A
C
B
D
F
E
d(B) = 3, d(C) = 2
Δ(G) = 3, δ(G) = 2
G

67. Graph Theory
Ch. 1. Fundamental Concept
67
Regular 1.3.1
G is regular if (G) =  (G)
G is k-regular if the common degree is k.
The neighborhood of v, written Ng(v) or N(v)
is the set of vertices adjacent to v.
3-regular

68. Graph Theory
Ch. 1. Fundamental Concept
68
Order and size 1.3.2
The order of a graph G, written n(G), is the
number of vertices in G.
An n-vertex graph is a graph of order n.
The size of a graph G, written e(G), is the number
of edges in G.
For nN, the notation [n] indicates the set {1,
…, n}.

69. Graph Theory
Ch. 1. Fundamental Concept
69
Proposition: (Degree-Sum Formula)
If G is a graph, then 
vV(G)d(v) = 2e(G) 1.3.3
Proof:
Summing the degrees counts each edge twice,
– Because each edge has two ends and contributes
to the degree at each endpoint.

70. Graph Theory
Ch. 1. Fundamental Concept
70
Theorem: If k>0, then a k-regular bipartite graph has
the same number of vertices in each partite set. 1.3.9
Proof:
Let G be an X,Y-bigraph.
Counting the edges according to their endpoints in
X yields e(G)=k|X|.
d (x) = k
x

71. Graph Theory
Ch. 1. Fundamental Concept
71
Theorem: If k>0, then a k-regular bipartite graph has
the same number of vertices in each partite set. 1.3.9
Proof:
Counting them by their endpoints in Y yields
e(G)=k|Y|.
Thus k|X|=k|Y|, which yields |X|=|Y| when k>0.
d (x) = k
x
d (y) = ky

72. Graph Theory
Ch. 1. Fundamental Concept
72
A technique for counting a set 1/3 1.3.10
Example: The Petersen graph has ten 6-cycles
–Let G be the Petersen graph.
–Being 3-regular, G has ten copies of K
1,3 (claw)
. We
establish a one-to-one correspondence between the 6-
cycles and the claws.
–Since G has girth 5, every 6-cycle F is an induced
subgraph.
•see below
–Each vertex of F has one neighbor outside F.
•d(v)= 3, v V(G)
If Existing, Girth =3.
But Girth=5 so no such an edge

73. Graph Theory
Ch. 1. Fundamental Concept
73
A technique for counting a set 2/3 1.3.10
–Since nonadjacent vertices have exactly one common
neighbor (Proposition 1.1.38), opposite vertices on F
have a common neighbor outside F.
–Since G is 3-regular, the resulting three vertices outside
F are distinct.
–Thus deleting V(F) leaves a subgraph with three vertices
of degree 1 and one vertex of degree 3; it is a claw.
Common neighbor
of opposite vertices
If the neighbors are
not distinct, d(v)>3

74. Graph Theory
Ch. 1. Fundamental Concept
74
A technique for counting a set 3/3 3.10
–It is shown that each claw H in G arises exactly once in
this way.
–Let S be the set of vertices with degree 1 in H; S is an
independent set.
–The central vertex of H is already a common neighbor,
so the six other edges from S reach distinct vertices.
–Thus G-V(H) is 2-regular. Since G has girth 5, G-V(H)
must be a 6-cycle. This 6-cycle yields H when its
vertices are deleted.

75. Graph Theory
Ch. 1. Fundamental Concept
75
Proposition: The minimum number of edges in a connected
graph with n vertices is n-1. 3.13
Proof:
By proposition 1.2.11, every graph with n vertices
and k edges has at least n-k components.
Hence every n-vertex graph with fewer than n-1
edges has at least two components and is
disconnected.
The contrapositive of this is that every connected n-
vertex graph has at least n-1 edges. This lower
bound is achieved by the path Pn.

76. Graph Theory
Ch. 1. Fundamental Concept
76
Theorem: If G is simple n-vertex graph with
(G)(n-1)/2, then G is connected. 1.3.15
Proof: 1/2
Choose u,v  V(G).
It suffices to show that u,v have a common neighbor
if they are not adjacent.
Since G is simple, we have |N(u) |   (G) 
(n-1)/2, and similarly for v.
–Recall:  (G) is the minimum degree, |N(u)| = d(u)
Hence: |N(u) |   (G)

77. Graph Theory
Ch. 1. Fundamental Concept
77
Theorem: If G is simple n-vertex graph with
(G)(n-1)/2, then G is connected. 1.3.15
Proof: 2/2
When u and v are not connected, we have |N(u)N(v)
| n-2
– since u and v are not in the union
Using Remark A.13 of Appendix A, we thus compute
| ( ) ( )| | ( )| | ( )| | ( ) ( )|
1 1
( 2) 1.
2 2
N u N v N u N v N u N v
n n
n
    
 
    

78. Graph Theory
Ch. 1. Fundamental Concept
78
Theorem: Every loopless graph G has a bipartite
subgraph with at least e(G)/2 edges. 1.3.19
Proof:
Partition V(G) into two sets X, Y.
Using the edges having one endpoint in each set yields a
bipartite subgraph H with bipartition X, Y.
If H contains fewer than half the edges of G incident to a
vertex v, then v has more edges to vertices in its own class
than in the other class, as illustrated bellow.

79. Graph Theory
Ch. 1. Fundamental Concept
79
Proof: 2/2
Moving v to the other class gains more edges of G
than it loses.
Using Iterative improvement approach
When it terminates, we have dH(v)  dG(v)/2 for
every vV(G) .
Summing this and applying the degree-sum formula
yields e(H)  e(G)/2.
Theorem: Every loopless graph G has a bipartite
subgraph with at least e(G)/2 edges. 1.3.19

80. Graph Theory
Ch. 1. Fundamental Concept
80
Example 1.3.20
The algorithm in Theorem 1.3.19 need not produce a
bipartite subgraph with the most edges, merely one
with at least half the edges. - Local Maximum.
Consider the graph in the next page.
–It is 5-regular with 8 vertices and hence has 20
edges.
–The bipartition X={a,b,c,d} and Y={e,f,g,h}
yields a 3-regular bipartite subgraph with 12
edges.
–The algorithm terminates here; switching one
vertex would pick up two edges but lose three .

81. Graph Theory
Ch. 1. Fundamental Concept
81
Example(Cont.) 1.3.20
a
b
c
de
f
g
h

82. Graph Theory
Ch. 1. Fundamental Concept
82
Example 1.3.20
Nevertheless, the bipartition X={a,b,g,h} and
Y={c,d,e,f} yields a 4-regular bipartite subgraph with
16 edges.
An algorithm seeking the maximal by local changes
may get stuck in a local maximum.
a
b
c
de
f
g
h
a
b
c
de
f
g
hLocal
Maximum
Global
Maximum

83. Graph Theory
Ch. 1. Fundamental Concept
83
Theorem: The maximum number of edges in an n-
vertex triangle free simple graph is  n
2
/4  1.3.23
Proof : 1/6
–Let G be an n-vertex triangle-free simple graph.
–Let x be a vertex of maximum degree and
d(x)=k.
–Since G has no triangles, there are no edges
among neighbors of x.
No edges between
neighbors of x

84. Graph Theory
Ch. 1. Fundamental Concept
84
Theorem: The maximum number of edges in an n-
vertex triangle free simple graph is  n
2
/4  1.3.23
Proof : 2/6
–Hence summing the degrees of x and its
nonneighbors counts at least one endpoint of every
edge: vN(x)d(v)  e(G).
–We sum over n-k vertices, each having degree at
most k, so e(G)  (n-k)k

85. Graph Theory
Ch. 1. Fundamental Concept
85
)(xN
x
x
)(xN
Doesn’t exist
• 
vN(x) d(v) counts at least
one endpoint of every edge
At most k vertices
At least n-k vertices
No edges exist
Theorem: The maximum number of edges in an n-
vertex triangle free simple graph is  n
2
/4  1.3.23
Proof: 3/6

86. Graph Theory
Ch. 1. Fundamental Concept
86
Proof: 4/6
–Since (n-k)k counts the edges in Kn-k, k, we have now
proved that e(G) is bounded by the size of some
biclique with n vertices.
•i.e. e(G)  (n-k)k = |the edges in Kn-k, k |
Theorem: The maximum number of edges in an n-
vertex triangle free simple graph is  n
2
/4  1.3.23
n-k k

87. Graph Theory
Ch. 1. Fundamental Concept
87
Proof: 5/6
–Moving a vertex of Kn-k,k from the set of size k to
the set of size n-k gains k-1 edges and loses n-k
edges.
–The net gain is 2k-1-n, which is positive for
2k>n+1 and negative for 2k<n+1.
–Thus e(K
n-k, k) is maximized when k is n/2  or
n/2 .
Theorem: The maximum number of edges in an n-
vertex triangle free simple graph is  n
2
/4  1.3.23
n-k k

88. Graph Theory
Ch. 1. Fundamental Concept
88
Proof: 6/6
–The product is then n
2
/4 for even n and (n
2
-1)/4 for
odd n. Thus e(G)  n
2
/4 .
–The bound is best possible.
•It is seen that a triangle-free graph with n
2
/4
edges is: Kn/2,n/2 .
Theorem: The maximum number of edges in an n-
vertex triangle free simple graph is  n
2
/4  1.3.23

89. Graph Theory
Ch. 1. Fundamental Concept
89
Degree sequence 1.3.27
The Degree Sequence of a graph is the list of vertex degrees,
usually written in non-increasing order, as d
1 ….  d
n .
Example:
z
y
x
w
v
Degree sequence:
d(w), d(x), d(y), d(z), d(v)

90. Graph Theory
Ch. 1. Fundamental Concept
90
Proposition: The nonnegative integers d
1 ,…, d
n are the
vertex degrees of some graph if and only if d
i is even.
1.3.28
Proof: ½ Necessity
When some graph G has these numbers as its vertex
degrees, the degree-sum formula implies that d
i = 2e
(G), which is even.

91. Graph Theory
Ch. 1. Fundamental Concept
91
Proof: 2/2 Sufficiency
Suppose that  d
i
is even.
We construct a graph with vertex set v
1
,…,v
n
and d(v
i
) = d
i
for all i.
Since  d
i
is even, the number of odd values is even.
First form an arbitrary pairing of the vertices in {v
i
: d
i
is odd}.
For each resulting pair, form an edge having these two vertices as
its endpoints
The remaining degree needed at each vertex is even and
nonnegative; satisfy this for each i by placing [d
i /2] loops at v
i
Proposition: The nonnegative integers d
1 ,…, d
n are the
vertex degrees of some graph if and only if d
i is even.
1.3.28

92. Graph Theory
Ch. 1. Fundamental Concept
92
Graphic Sequence 1.3.29
A graphic sequence is a list of nonnegative
numbers that is the degree sequence of some
simple graph.
A simple graph “realizes” d.
–means: A simple graph with degree
sequence d.

93. Graph Theory
Ch. 1. Fundamental Concept
93
Recursive condition 1.3.30
The lists (2, 2, 1, 1) and (1, 0, 1) are graphic. The graphic
K
2+K
1 realizes 1, 0, 1.
Adding a new vertex adjacent to vertices of degrees 1 and 0
yields a graph with degree sequence 2, 2, 1, 1, as shown below.
Conversely, if a graph realizing 2, 2, 1, 1 has a vertex w with
neighbors of degrees 2 and 1, then deleting w yields a graph
with degrees 1, 0, 1.
w

94. Graph Theory
Ch. 1. Fundamental Concept
94
Recursive condition 1.3.30
Similarly, to test 33333221, we seek a realization
with a vertex w of degree 3 having three neighbors
of degree 3.
3 3 3 3 3 2 2 1
2 2 2 3 2 2 1
Delete this
Vertex
A new
degree sequence

95. Graph Theory
Ch. 1. Fundamental Concept
95
Recursive condition 1.3.30
This exists if and only if 2223221 is graphic. (See next page)
–We reorder this and test 3222221.
–We continue deleting and reordering until we can tell
whether the remaining list is realizable.
–If it is, then we insert vertices with the desired neighbors
to walk back to a realization of the original list.
–The realization is not unique.
The next theorem implies that this recursive test work.

96. Graph Theory
Ch. 1. Fundamental Concept
96
Recursive condition 1.3.30
33333221 3222221 221111 11100
2223221 111221 10111
wv
u u
v
u

97. Graph Theory
Ch. 1. Fundamental Concept
97
Theorem. For n>1, an integer list d of size n is graphic if and
only if d’ is graphic, where d’ is obtained from d by deleting
its largest element  and subtracting 1 from its  next largest
elements. The only 1-element graphic sequence is d
1
=0. 1.3.31
Proof: 1/6
For n=1, the statement is trivial.
For n>1, we first prove that the condition is sufficient.
–Give d with d
1…..d
n and a simple graph G’ with
degree sequence d’
For Example:
We have: 1) d=33333221

2) G’ with d’ = 2223221
We show: d is graphic
G’

98. Graph Theory
Ch. 1. Fundamental Concept
98
Theorem. For n>1, an integer list d of size n is graphic if and
only if d’ is graphic, where d’ is obtained from d by deleting
its largest element  and subtracting 1 from its  next largest
elements. The only 1-element graphic sequence is d
1
=0. 1.3.31
Proof: 2/6
–We add a new vertex adjacent to vertices in G’ with
degrees d
2-1,…..,d
+1-1.
–These d
i
are the  largest elements of d after (one copy
of)  itself,
–Note : d
2-1,…..,d
+1-1 need not be the  largest numbers
in d’ (see example in previous page)
G’
New added
vertex
d : d
1,d
2,… d
n
d’ : d
2-1,…..,d
+1-1,… d
n
May not be the 
largest numbers

99. Graph Theory
Ch. 1. Fundamental Concept
99
Theorem
1.3.31 continue
To prove necessity, 3/6
–Given a simple graph G realizing d , we produce
•A simple graph G’ realizing d’.
–Let w be a vertex of degree  in G, and let S be a set of 
vertices in G having the “desired degrees” d
2,…..,d
+1.
d : d
1,
d
2,
…d
, d
+1,
… d
n
S:  verticesd
1
=
w

100. Graph Theory
Ch. 1. Fundamental Concept
100
Theorem
1.3.31
Proof: continue 4/6
–If N(w)=S, then we delete w to obtain G’.
d : d
1,
d
2,
…d
, d
+1,
… d
n
Vertices, N(w)=S
i.e. They are connected to w
d
1
=
w
Delete w than we have
d’ : d
2-1,…..,d
+1-1
,
… d
n

101. Graph Theory
Ch. 1. Fundamental Concept
101
Theorem
1.3.31
Proof: continue 5/6
–Otherwise,
•Some vertex of S is missing from N(w).
•In this case, we modify G to increase |N(w)S| without
changing any vertex degree.
•Since |N(w)S| can increase at most  times, repeating this
converts G into another graph G* that realizes d and has S as
the neighborhood of w.
•From G* we then delete w to obtain the desired graph G’
realizing d’.
d : d
1,
d
2,
…d
, d
+1,
… d
n
Vertices, N(w)S
i.e. Some vertices are not connected to w.
- We make them become connected to w
without changing their degree.
d
1
=
w

102. Graph Theory
Ch. 1. Fundamental Concept
Theorem
1.3.31
Proof: continue6/6
•To find the modification when N(w)S , we choose xS
and zS so that w z are connected and w x are not.
•We want to add wx and delete wz, but we must preserve
vertex degrees. Since d(x)>d(z) and already w is a
neighbor of z but not x, there must be a vertex y adjacent to
x but not to z. Now we delete {wz,xy} and add {wx,yz} to
increase |N(w)S| .
w
z
x
y
This y must exist.
w
z
x
y

It becomes connected w

103. Graph Theory
Ch. 1. Fundamental Concept
103
2-switch 1.3.32
A 2-switch is the replacement of a pair of edges xy
and zw in a simple graph by the edges yz and wx,
given that yz and wx did not appear in the graph
originally.
wx
y z y z
wx

104. Graph Theory
Ch. 1. Fundamental Concept
104
Theorem: If G and H are two simple graphs with vertex set V,
then d
G(v)=d
H(v) for every vV if and only if there is a
sequence of 2-switches that transforms G into H. 1.3.33
Proof:
Every 2-switch preserves vertex degrees, so the
condition is sufficient.
Conversely, when d
G
(v)=d
H
(v) for all vV , we obtain
an appropriate sequence of 2-switches by induction on
the number of vertices, n.
If n<3, then for each d
1,…..,d
n there is at most one
simple graph with d(vi)=d
i
.
Hence we can use n=3 as the basis step.

105. Graph Theory
Ch. 1. Fundamental Concept
105
Theorem. 1.3.33 (Continue)
Consider n4 , and let w be a vertex of maximum degree,.
Let S={v
1,…..,v
} be a fixed set of vertices with the 
highest degrees other than w.
As in the proof of Theorem 1.3.31, some sequence of 2-
switches transforms G to a graph G* such that N
G*(w)=S,
and some such sequence transforms H to a graph H* such
that N
H*(w)=S.
Since N
G*(w)=N
H*(w), deleting w leaves simple graphs
G’=G*-w and H’=H*-w with d
G’(v)=d
H’(v) for every vertex
v.

106. Graph Theory
Ch. 1. Fundamental Concept
106
Theorem. 1.3.33 Continue
By the induction hypothesis, some sequence of 2-switches
transforms G’ to H’. Since these do not involve w, and w has
the same neighbors in G* and H*, applying this sequence
transforms G* to H*.
Hence we can transform G to H by transforming G to G*, then
G* to H*, then (in reverse order) the transformation of H to H*.

107. Graph Theory
Ch. 1. Fundamental Concept
107
Directed Graph and Its edges 1.4.2
A directed graph or digraph G is a triple:
–A vertex set V(G),
–An edge set E(G), and
–A function assigning each edge an ordered pair of
vertices.
•The first vertex of the ordered pair is the tail of the edge
•The second is the head
•Together, they are the endpoints.
An edge is said to be from its tail to its head.
–The terms “head” and “tail” come from the arrows used
to draw digraphs.

108. Graph Theory
Ch. 1. Fundamental Concept
108
Directed Graph and its edges 1.4.2
As with graphs, we
–assign each vertex a point in the plane and
–each edge a curve joining its endpoints.
When drawing a digraph, we give the curve a direction from
the tail to the head.

109. Graph Theory
Ch. 1. Fundamental Concept
109
Directed Graph and its edges 1.4.2
When a digraph models a relation, each ordered pair is the
(head, tail) pair for at most one edge.
–In this setting as with simple graphs, we ignore the
technicality of a function assigning endpoints to edges and
simply treat an edge as an ordered pair of vertices.

110. Graph Theory
Ch. 1. Fundamental Concept
110
Loop and multiple edges in directed graph 1.4.3
In a graph, a loop is an edge whose endpoints are equal.
Multiple edges are edges having the same ordered pair of
endpoints.
A digraph is simple if each ordered pair is the head and tail
of the most one edge; one loop may be present at each vertex.
Loop
Multiple
edges

111. Graph Theory
Ch. 1. Fundamental Concept
111
Loop and multiple edges in directed graph 1.4.3
In the simple digraph, we write uv for an edge with
tail u and head v.
–If there is an edge form u to v, then v is a
successor of u, and u is a predecessor of v.
–We write uv for “there is an edge from u to v”.
Predecessor
Successor

112. Graph Theory
Ch. 1. Fundamental Concept
112
Path and Cycle in Digraph 1.4.6
A digraph is a path if it is a simple digraph whose
vertices can be linearly ordered so that there is an
edge with tail u and head v if and only if v
immediately follows u in the vertex ordering.
A cycle is defined similarly using an ordering of
the vertices on the cycle.

113. Graph Theory
Ch. 1. Fundamental Concept
113
Underlying graph 1.4.9
The underlying graph of a digraph D:
–the graph G obtained by treating the edges of D as
unordered pairs;
–the vertex set and edges set remain the same, and
the endpoints of an edge are the same in G as in D,
–but in G they become an unordered pair.
The underlying GraphA digraph

114. Graph Theory
Ch. 1. Fundamental Concept
114
Underlying graph 1.4.9
Most ideals and methods of graph theorem arise in the study of
ordinary graphs.
Digraphs can be a useful additional tool, especially in
applications
When comparing a digraph with a graph, we usually use G for
the graph and D for the digraph. When discussing a single
digraph, we often use G.

115. Graph Theory
Ch. 1. Fundamental Concept
115
Adjacency Matrix and Incidence Matrix
of a Digraph 1.4.10
In the adjacency matrix A(G) of a digraph G, the
entry in position i, j is the number of edges from v
i
to v
j
.
In the incidence matrix M(G) of a loopless
digraph G, we set m
i,j=+1 if v
i is the tail of e
j and
m
i,j= -1 if v
i is the head of e
j.

116. Graph Theory
Ch. 1. Fundamental Concept
116
Example of adjacency matrix 1.4.11
The underlying graph of the digraph below is the graph
of Example 1.1.19; note the similarities and differences
in their matrices.












0000
1010
0101
0100
















10000
11110
01101
00011
wxyz
w
x
y
z
w
x
y
z
abcde
)(GA G )(GM
a
b
ec
d
w
x
y
z

117. Graph Theory
Ch. 1. Fundamental Concept
117
Connected Digraph 1.4.12
To define connected digraphs, two options come to mind.
We could require only that the underlying graph be
connected.
However, this does not capture the most useful sense of
connection for digraphs.

118. Graph Theory
Ch. 1. Fundamental Concept
118
Weakly and strongly connected
digraphs 1.4.12
A graph is weakly connected if its underlying graph is
connected.
A digraph is strongly connected or strong if for each
ordered pair u,v of vertices, there is a path from u to v.

119. Graph Theory
Ch. 1. Fundamental Concept
119
Eulerian Digraph 1.4.22
An Eulerian trail in digraph (or graph) is a trail
containing all edges.
An Eulerian circuit is a closed trail containing all
edges.
A digraph is Eulerian if it has an Eulerian circuit.

120. Graph Theory
Ch. 1. Fundamental Concept
120
Lemma. If G is a digraph with 
+
(G)1, then G
contains a cycle. The same conclusion holds
when 
-
(G) 1. 1.4.23
Proof.
Let P be a maximal path in G, and u be the last vertex
of P.
Since P cannot be extended, every successor of u
must already be a vertex of P.
Since 
+
(G)1, u has a successor v on P.
The edge uv completes a cycle with the portion of P
from v to u.

121. Graph Theory
Ch. 1. Fundamental Concept
121
Theorem: A digraph is Eulerian if and only if d
+
(v)=d
-
(v) for each vertex v and the underlying
graph has at most one nontrivial component.
1.4.24

122. Graph Theory
Ch. 1. Fundamental Concept
122
De Bruijn cycles 1.4.25
Application:
–There are 2
n
binary strings of length n.
–Is there a cyclic arrangement of 2
n
binary digits such that the
2
n
strings of n consecutive digitals are all distinct?
–Example: For n=4, (0000111101100101) works.
0000 0001 0011 0111 1111 1110 1101 1011 …
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1

123. Graph Theory
Ch. 1. Fundamental Concept
123
De Bruijn cycles 1.4.25
We can use such an arrangement to keep track of the position
of a rotating drum.
–One drum has 2
n
rotational positions.
–A band around the circumference is split into 2
n
portions
that can be coded 0 or 1.
–Sensors read n consecutive portions.
–If the coding has the property specified above, then the
position of the drum is determined by the string read by
the sensors.

124. Graph Theory
Ch. 1. Fundamental Concept
124
De Bruijn cycles 1.4.25
To obtain such a circular arrangement,
–define a digraph D
n whose vertices are the binary (n-1)-
tuples.
–Put an edge from a to b if the last n-2 entries of a agree
with the first n-2 entries of b.
–Label the edge with the last entry of b.
Below we show D
4. We next prove that D
n is Eulerian and
show how an Eulerian circuit yields the desired circular
arrangement.

125. Graph Theory
Ch. 1. Fundamental Concept
125
De Bruijn cycles 1.4.25
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0 0
0
0
0
0
0
1
1
1
1
1
1
1
1
001
000
100
010 101
011
110
111
a b
Put an edge from a to b if the last n-2
entries of a agree with the first n-2
entries of b.
Label the edge with the last entry of
b.

126. Graph Theory
Ch. 1. Fundamental Concept
126
Theorem. The digraph D
n
of Application 1.4.25 is
Eulerian, and the edge labels on the edges in any
Eulerian circuit of D
n
form a cyclic arrangement in
which the 2
n
consecutive segments of length n are
distinct. 1.4.26
Proof:
We show
–first that D
n
is Eulerian.
–Then the labels on the edges in any Eulerian
circuit of D
n form a cyclic arrangement in which
the 2
n
consecutive segments of length n are
distinct.

127. Graph Theory
Ch. 1. Fundamental Concept
127
Theorem. The digraph D
n is Eulerian 1.4.26
Proof: 1/2
Every vertex has out-degree 2
–because we can append a 0 or a 1 to its name to obtain the
name of a successor vertex.
Similarly, every vertex has in-degree 2,
–because the same argument applies when moving in reverse
and putting a 0 or a 1 on the front of the name.
001
101
011
110
111

128. Graph Theory
Ch. 1. Fundamental Concept
128
Theorem. The digraph D
n
is Eulerian 1.4.26
Proof: 2/2
Also, D
n is strongly connected,
–because we can reach the vertex b=(b
1,…..,b
n-1) from
any vertex by successively follows the edges labeled
b
1,…..,b
n-1.
Thus D
n satisfies the hypotheses of Theorem 1.4.24 and
is Eulerian.
0
0 0
0
0
0
0
0
1
1
1
1
1
1
1
001
000
100
010 101
011
110
111
a b
1
1

129. Graph Theory
Ch. 1. Fundamental Concept
129
Theorem. The labels on the edges in any Eulerian circuit of D
n

form a cyclic arrangement in which the 2
n
consecutive
segments of length n are distinct. 1.4.26
Proof: 1/4
Let C be an Eulerian circuit of D
n
. Arrival at vertex
a=(a
1,…..,a
n-1) must be along an edge with label a
n-1
–because the label on an edge entering a vertex
agrees with the last entry of the name of the vertex.
0
0 0
0
0
0
0
0
1
1
1
1
1
1
1
1
001
000
100
010 101
011
110
111
a b

130. Graph Theory
Ch. 1. Fundamental Concept
130
Theorem. The labels on the edges in any Eulerian circuit of D
n
form a cyclic arrangement in which the 2
n
consecutive
segments of length n are distinct. 1.4.26
Proof: 2/4
The successive earlier labels (looking backward)
must have been a
n-2,…..,a
1 in order.
–because we delete the front and shift the reset to
obtain the reset of the name at the head
0
0 0
0
0
0
0
0
1
1
1
1
1
1
1
1
001
000
100
010 101
0 1 1
110
111
a b

131. Graph Theory
Ch. 1. Fundamental Concept
131
Theorem. The labels on the edges in any Eulerian circuit of D
n
form a cyclic arrangement in which the 2
n
consecutive
segments of length n are distinct. 1.4.26
Proof: 2/4
If C next uses an edge with label a
n, then the list
consisting of the n most recent edge labels at that time
is a
1
,…..a
n
.
0
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
001
000
100
010 101
011
110
111
a b
0
1

132. Graph Theory
Ch. 1. Fundamental Concept
132
Theorem. The labels on the edges in any Eulerian circuit of
D
n form a cyclic arrangement in which the 2
n
consecutive
segments of length n are distinct. 1.4.26
Proof: 3/4
Since
–the 2
n-1
vertex labels are distinct, and
–the two out-going edges have distinct labels, and
–we traverse each edge exactly once
011 0
011 1
Distinct
vertex label
Distinct labels on
out-going edges

133. Graph Theory
Ch. 1. Fundamental Concept
133
Theorem. The labels on the edges in any Eulerian circuit of
D
n form a cyclic arrangement in which the 2
n
consecutive
segments of length n are distinct. 1.4.26
Proof: 4/4
We have shown that the 2
n
strings of length n in the
circular arrangement given by the edge labels along
C are distinct.