graph theory in applied mathematics with example

Graph theory concepts

1. Unit III
Graph Theory
Graph Theory 1

2. 2Graph Theory
1.1 What Is a Graph?
1.2 Paths, Cycles, and Trails
1.3 Vertex Degree and Counting
1.4 Directed Graphs

3. 3
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.
Graph Theory
3
X
Y
Z
W

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

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

6. 6
Loop, Multiple edges
Loop: An edge whose endpoints are equal
Multiple edges: Edges have the same pair of
endpoints
Graph Theory
6
loop
Multiple
edges

7. 7Graph Theory
7
Simple Graph
Simple graph: A graph has no loops or multiple
edges
loop
Multiple
edges
It is notsimple. It is a simplegraph.

8. 8
Adjacent, neighbors
Two vertices are adjacentand are neighbors
if they are the endpoints of an edge.
Example:
Aand Bare adjacent.
Aand Dare not adjacent.
Graph Theory
8
A B
C D

9. 9
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.
Graph Theory
9

10. 10
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) }
Graph Theory
10
G
u
v
w
x
y
G’
u
v
wx
y

11. 11
Clique and Independent set
A Cliquein a graph: a set of pairwise
adjacent vertices (a complete subgraph)
An independent setin a graph: a set of
pairwise nonadjacent vertices.
Example:
{x, y, u} is a clique in G.
{u, w} is an independent set.
Graph Theory
11
G
u
v
w
x
y

12. 12
Bipartite Graphs
A graph Gis bipartiteif V(G) is the union
of two disjoint independent sets called
partite sets ofG
Also: The vertices can be partitionedinto
two sets such that each set is independent
Matching Problem
Job Assignment Problem
Graph Theory
12
Workers
Jobs
Boys
Girls

13. 13
Chromatic Number
The chromatic numberof a graph G,
written x(G), is the minimum number of
colors needed to label the vertices so that
adjacent vertices receive different colors
Graph Theory
13
Red
Green
Blue
Blue
x(G) = 3

14. 14
Maps and coloring
A mapis a partition of the plane into
connected regions
Can we color the regions of every map using at
most four colorsso that neighboring regions
have different colors?
Map Coloring graph coloring
A region A vertex
Adjacency An edge
Graph Theory
14

15. 15
Scheduling and graph Coloring 1
Two committees can not hold meetings at the
same time if two committees have common
member
Graph Theory
15
common
member
Committee 1 Committee 2

16. 16
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
Graph Theory
16
common
member
Committee 1 Committee 2

17. 17
Scheduling and graph Coloring 2
Scheduling problem is equivalent to graph
coloring problem.
Graph Theory
17
common
member
Committee 1
Committee 2
Committee 3
Common Member
Different Color
No Common Member
Same Color OK
Same time slot OK

18. 18
Path and Cycle
Path: a sequence of distinctvertices 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
Graph Theory
18
a b
c
d
e

19. 19
Subgraphs
A subgraphof a graph Gis a graph Hsuch
that:
V(H) V(G) and E(H) E(G) and
The assignment of endpoints to edges in His
the same as in G.
Graph Theory
19

20. 20
Subgraphs
Example: H
1, H
2, and H
3are subgraphs of
G
Graph Theory
20
c
d
a b
d
e
a
b
c
de
H
1
G
H
3
H
2
a b
c
d
e

21. 21
Connected and Disconnected
Connected: There exists at least one path
between two vertices.
Disconnected: Otherwise
Example:
H
1and H
2are connected.
H
3is disconnected.
Graph Theory
21
c
d
a
b
d
e
a b
c
de
H
1
H
3H
2

22. 22
Adjacency, Incidence, and Degree
Assume e
iis an edge whose endpoints are
(v
j,v
k)
The vertices v
jand v
kare said to be adjacent.
The edge e
i is said to be incident uponv
j
Degreeof a vertex v
k is the number of edges
incident upon v
k . It is denoted as d(v
k)
Graph Theory
22
e
i
v
j
v
k

23. 23
Adjacency matrix
Let G= (V, E), |V| = nand |E|=m
The adjacency matrixofGwritten A(G), is the
n-by-nmatrix in which entry a
i,jis the number
of edges in Gwith endpoints {v
i, v
j}.
Graph Theory
23
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

24. 24
Incidence Matrix
Let G= (V, E), |V| = nand |E|=m
The incidence matrixM(G) is the n-by-m
matrix in which entry m
i,jis 1 if v
iis an
endpoint of e
iand otherwise is 0.
Graph Theory
24
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

25. 25
Isomorphism
An isomorphismfrom a simple graph Gto a
simple graph His 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
Graph Theory
25
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

26. 26
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.
Graph Theory
26
Complete Graph Complete Bipartite Graph

27. 27
Petersen Graph 1.1.36
The petersen graphis 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
Graph Theory
27

28. 28
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)
Graph Theory
28
Disjoint, so
connected
45: (4, 5)
12
34
15
23
45
35
13
14
24
25

29. 29
Petersen Graph 1.1.36
Three drawings
Graph Theory
29

30. 30
Theorem:If two vertices are non-adjacent in the
Petersen Graph, then they have exactly one common
neighbor. 1.1.38
Proof:
Graph Theory
30
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

31. 31
Girth 1.1.39, 1.1.40
Girth: the length of its shortest cycle.
If no cycles, girth is infinite
Graph Theory
31

32. 32
Girth and Petersen graph1.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.
Graph Theory
32

33. 33
Walks, Trails1.2.2
A walk:a list of vertices and edges v
0, e
1,
v
1, …., e
k, v
ksuch that, for 1ik, the edge
e
ihas endpoints v
i-1and v
i.
A trail: a walk with no repeated edge.
Graph Theory
33

34. 34
Paths1.2.2
A u,v-walk or u,v-trail has first vertex uand
last vertex v; these are its endpoints.
A u,v-path: a u,v-trail with no repeated
vertex.
The lengthof a walk, trail, path, or cycle is
its number of edges.
A walk or trail is closedif its endpoints are
the same.
Graph Theory
34

35. 35
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, Wconsists of a single vertex
(u=v).
This vertex is a u,v-path of length 0.
to be continued
Graph Theory
35

36. 36
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 Whas no repeated vertex, then its vertices and
edges form a u,v-path.
If Whas 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 Pis contained in W.
Graph Theory
36

37. 37
Lemma:Every u,v-walk contains a u,v-path 1.2.5
An example:
Graph Theory
37u v W P
Delete

38. 38
Components 1.2.8
The componentsof a graph G are its
maximalconnected subgraphs.
A component (or graph) is trivialif it has no
edges; otherwise it is nontrivial.
An isolated vertexis a vertex of degree 0.
Graph Theory
38r q s u v w t p x y z

39. 39
Theorem: Every graph with nvertices and kedges
has at least n-kcomponents 1.2.11
Proof:
An n-vertex graph with no edges has n
components
Each edge added reduces this by at most 1
If kedges are added, then the number of
components is at least n-k
Graph Theory
39

40. 40
Theorem:Every graph with nvertices and kedges has
at least n-kcomponents 1.2.11
Examples:
Graph Theory
40
n=2, k=1,
1 component
n=3, k=2,
1 component
n=6, k=3,
3 components
n=6, k=3,
4 components

41. 41
Cut-edge, Cut-vertex 1.2.12
A cut-edgeor cut-vertexof a graph is an
edge or vertex whose deletion increases the
number of components.
Graph Theory
41
Not a Cut-vertex
Cut-edge
Cut-edge
Cut-vertex

42. 42
Cut-edge, Cut-vertex 1.2.12
G-eor G-M: The subgraph obtained by
deleting an edge eor set of edges M.
G-v or G-S: The subgraph obtained by
deleting a vertex vor set of vertices S.
Graph Theory
42
e
G-eG

43. 43
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 Ginduced by T.
Example:
Assume T:{A, B, C, D}
Graph Theory
43
B
A
C D
E
B
A
C D
G[T]
G

44. 44
Induced subgraph 1.2.12
More Examples:
G
2is the subgraph of G
1induced by (A, B, C, D)
G
3is the subgraph of G
1induced by (B, C)
G4is notthe subgraph induced by (A, B, C, D)
Graph Theory
44
B
A
C D
E
B
A
C D
B
C
B
A
C D
G1 G2
G3 G4

45. 45
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.
G3 is an example.
Graph Theory
45
B
A
C D
E
B
C
G1
G3

46. 46
Theorem:An edgeeis a cut-edge if and only if e
belongs to nocycles.1.2.14
Proof :1/2
Let e= (x, y) be an edge in a graph Gand Hbe the
component containing e.
Since deletion of eeffects 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-eis connected.
This implies that H-econtains an x, y-path,
This path completes a cycle with e.
Graph Theory
46

47. 47
Theorem:An edgeeis a cut-edge if and only if e
belongs to nocycles.1.2.14
Proof :2/2
Now suppose that elies in a cycle C.
Choose u, vV(H)
Since His connected, Hhas a u, v-path P.
If Pdoes not contain e
Then Pexists in H-e
Otherwise
Suppose by symmetry that xis between uand yon P
Since H-econtains 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-eis
connected.
Graph Theory
47

48. 48
Theorem:An edgeeis a cut-edge if and only
if e belongs to nocycles. 1.2.14
An Example:
Graph Theory
48u x y e P C v

49. 49
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.
Graph Theory
49

50. 50
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 Whas no repeated vertex (other than first = last),
then Witself forms a cycle of odd length.
Otherwise,
Need to prove: If repeated, Wincludes a shorter closed
odd walk. By induction, the theorem hold
If Whas a repeated vertex v, then we view Was
starting at vand break Winto 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.
Graph Theory
50

51. 51
Lemma:Every closed odd walk contains an odd
cycle 1.2.15
Graph Theory
51
Even
v
Odd
Odd = Odd + Even

52. 52
Theorem:A graph is bipartite if and only if it has no
odd cycle. 1.2.18
Examples:
Graph Theory
52
B
A
D C
A
C
B
D
A
C
B
D
F
E
A
C
B
D
E F

53. 53
Theorem:A graph is bipartite if it has no odd cycle. 1.2.18
Proof: (sufficiency1/3)
Let Gbe a graph with no odd cycle.
We prove that Gis bipartite by constructing a bipartition of each
nontrivial component H.
For each vV(H), letf(v) be the minimum length of a u, v-path.
Since His connected, f(v) is defined for each vV(H) .
Graph Theory
53u v 'v ( ')fv ()fv

54. 54
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 (orY)and the
reverse of a shortest u, v’-path.
Graph Theory
54u v 'v
A closed odd walk using
1)a shortest u, v-path,
2)the edge v, v’ within X (orY), and
3)the reverse of a shortest u, v’-path.

55. 55
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 Xand Yare independent sets. Also XY=V(H), so His
an X, Y-bipartite graph
Graph Theory
55u 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:
Xand Yare independent sets

56. 56
Theorem: A graph is bipartite only if it has no
odd cycle.1.2.18
Proof: (necessity)
Let Gbe 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 Ghas no odd cycle
Graph Theory
56

57. 57
Eulerian Circuits 1.2.24
A graph is Eulerianif it has a closed trail
containing all edges.
We call a closed trail a circuitwhen we do
not specify the first vertex but keep the list
in cyclic order.
An Eulerian circuitor Eulerian trailin a
graph is a circuit or trail containing all the
edges.
Graph Theory
57

58. 58
Even Graph, Even Vertex, and Maximal Path1.2.24
An even graphis a graph with vertex
degrees all even.
A vertex is odd[even] when its degree is
odd [even].
A maximal pathin a graph Gis a path Pin
Gthat is not contained in a longer path.
When a graph is finite, no path can extend
forever , so maximal (non-extendible) paths
exist.
Graph Theory
58

59. 59
Lemma:If every vertex of graph Ghas degree at
least 2, then Gcontains a cycle.1.2.25
Proof:
Let Pbe a maximal path in G, and letube an endpoint of P
SincePcannot be extended, every neighbor of umust already be
a vertex of P
Since uhas degree at least 2, it has a neighbor vin V(P) via an
edge not in P
The edge uvcompletes a cycle with the portion of Pfrom vto u
Graph Theory
59
uP
Impossible
v
P
u
Must

60. 60
Theorem:A graph Gis 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 Ghas an Eulerian circuit C.
Each passage of Cthrough 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.
Graph Theory
60

61. 61
Theorem:A graph Gis 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. →
Graph Theory
61

62. 62
Theorem:A graph Gis 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 Ghas degree at least 2.
By Lemma 1.2.25, the nontrivial component has a cycle C.
Let G’ be the graph obtained from Gby deleting E(C).
SinceChas0 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. →
Graph Theory
62

63. 63
Theorem:A graph Gis 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.
Graph Theory
63

64. 64
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
Graph Theory
64

65. 65
Proposition:If Gis a simple graph in which every vertex has
degree at least k, then Gcontains a path of length at least k.
Ifk2, then Galso contains a cycle of length at least k+1.
1.2.28
Proof: (1/2)
Let ube an endpoint of a maximal path Pin
G.
Since P does not extend, every neighbor of
u is inV(P).
Since uhas at least kneighbors and Gis
simple, Ptherefore has at least kvertices
other than uand has length at least k.
Graph Theory
65

66. 66
Proposition:If Gis a simple graph in which every vertex has
degree at least k, then Gcontains a path of length at least k.
Ifk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 uto its farthest
neighbor valong Pcompletes a sufficiently
long cycle with the portion of P from vto u.
Graph Theory
66
u
v
d(u) k
At least k+1 vertices
Length k

67. 67
Degree1.3.1
The degreeof vertex vin 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 degreeis (G)
The minimum degreeis (G)
Graph Theory
67
A
C
B
D
F
E
d(B) = 3, d(C) = 2
Δ(G) = 3, δ(G) = 2
G

68. 68
Regular 1.3.1
Gis regularif (G) = (G)
Gis k-regularif the common degree is k.
The neighborhoodof v, written Ng(v) or N(v)
is the set of vertices adjacent to v.
Graph Theory
68
3-regular

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

70. 70
Proposition:(Degree-Sum Formula)
If Gis 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.
Graph Theory
70

71. 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:
Let Gbe an X,Y-bigraph.
Counting the edges according to their
endpoints in Xyields e(G)=k|X|.
Graph Theory
71
d(x) = k
x

72. 72
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.
Graph Theory
72
d(x) = k
x
d(y) = ky

73. 73
A technique for counting a set1/31.3.10
Example: The Petersen graph has ten 6-cycles
Let Gbe the Petersen graph.
Being 3-regular, Ghas ten copies of K1,3 (claw). We
establish a one-to-one correspondence between the 6-cycles
and the claws.
Since Ghas girth 5, every 6-cycle Fis an induced subgraph.
see below
Each vertex of Fhas one neighbor outside F.
d(v)= 3, v V(G)
Graph Theory
73
If Existing, Girth =3.
But Girth=5 so no such an edge

74. 74Graph Theory
74
A technique for counting a set 2/31.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 Gis 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

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

76. 76
Proposition: The minimum number of edges in a connected
graph with nvertices is n-1. 3.13
Proof:
By proposition 1.2.11, every graph with n
vertices and kedges 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.
Graph Theory
76

77. 77
Theorem: If Gis simple n-vertex graph with
(G)(n-1)/2, then Gis connected. 1.3.15
Proof:1/2
Choose u,v V(G).
It suffices to show that u,vhave 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)
Graph Theory
77

78. 78
Theorem: If Gis simple n-vertex graph with
(G)(n-1)/2, then Gis connected. 1.3.15
Proof:2/2
When uand vare not connected, we have |N(u)N(v)
|n-2
since uand vare not in the union
Using Remark A.13 of Appendix A, we thus compute
Graph Theory
78 | ( ) ( )| | ( )| | ( )| | ( ) ( )|
11
( 2) 1.
22
N u N v N u N v N u N v
nn
n
    

    

79. 79
Theorem: Every loopless graph Ghas 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 Hwith bipartition X, Y.
If Hcontains fewer than half the edges of G incident to a
vertex v, then vhas more edges to vertices in its own class than
in the other class, as illustrated bellow.
Graph Theory
79

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

81. 81
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 .
Graph Theory
81

82. 82
Example(Cont.) 1.3.20
Graph Theory
82a b c d e f g h

83. 83
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.
Graph Theory
83a b c d e f g h a b c d e f g h
Local
Maximum
Global
Maximum

84. 84
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 Gbe an n-vertex triangle-free simple graph.
Let x be a vertex of maximum degree and
d(x)=k.
Since Ghas no triangles, there are no edges
among neighbors of x.
Graph Theory
84
No edges between
neighbors of x

85. 85
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 xand its
nonneighbors counts at least one endpoint of
every edge: vN(x)d(v) e(G).
We sum over n-kvertices, each having degree
at most k, so e(G) (n-k)k
Graph Theory
85

86. 86Graph Theory
86)(xN x x )(xN
Doesn’t exist
•
vN(x)d(v) counts at least
one endpoint of every edge
At mostkvertices
At least n-kvertices
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

87. 87
Proof:4/6
Since (n-k)kcounts the edges in Kn-k, k, we have
now proved that e(G) is bounded by the size of
some biclique with nvertices.
i.e. e(G) (n-k)k = |the edges in Kn-k, k |
Graph Theory
87
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. 88Graph Theory
88
Proof:5/6
–Moving a vertex of Kn-k,kfrom the set of size kto
the set of size n-kgains k-1edges 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(Kn-k, k) is maximized when kis 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

89. 89
Proof:6/6
The product is then n
2
/4 for even nand (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 .
Graph Theory
89
Theorem: The maximum number of edges in an n-
vertex triangle free simple graph is n
2
/41.3.23

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

91. 91
Proposition:The nonnegative integers d
1 ,…, d
nare the
vertex degrees of some graph if and only if diis even.
1.3.28
Proof:½ Necessity
When some graph Ghas these numbers as its vertex
degrees, the degree-sum formula implies that d
i= 2e (G),
which is even.
Graph Theory
91

92. 92
Proof:2/2Sufficiency
Suppose that d
iis even.
We construct a graph with vertex set v
1,…,v
nand d(v
i) = d
ifor all
i.
Since d
iis even, the number of odd values is even.
First form an arbitrary pairing of the vertices in {v
i: d
iis 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 iby placing [d
i/2] loops at v
i
Graph Theory
92
Proposition:The nonnegative integers d
1 ,…, d
nare the
vertex degrees of some graph if and only if diis even.
1.3.28

93. 93
Graphic Sequence 1.3.29
A graphic sequenceis a list of nonnegative
numbers that is the degree sequence of some
simplegraph.
A simple graph “realizes” d.
means: A simple graph with degree sequence
d.
Graph Theory
93

94. 94
Recursive condition 1.3.30
The lists (2, 2, 1, 1) and (1, 0, 1) are graphic. The graphic
K2+K1realizes 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 wwith
neighbors of degrees 2 and 1, then deleting wyields a graph
with degrees 1, 0, 1.
Graph Theory
94w

95. 95
Recursive condition 1.3.30
Similarly, to test 33333221, we seek a realization
with a vertex wof degree 3 having three neighbors of
degree 3.
Graph Theory
95
33 3 33 2 2 1
2 2 23 2 2 1
Delete this
Vertex
A new
degree sequence

96. 96
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.
Graph Theory
96

97. 97
Recursive condition 1.3.30
33333221 3222221 221111
11100
2223221 111221 10111
Graph Theory
97w v u u v u

98. 98
Theorem.For n>1, an integer list dof size nis graphic if and
only if d’is graphic, where d’is obtained from dby 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 dwith d
1…..d
nand a simple graph G’with
degree sequence d’
Graph Theory
98
For Example:
We have: 1) d=33333221
2) G’with d’ = 2223221
Weshow: dis graphic
G’

99. 99
Theorem.For n>1, an integer list dof size nis graphic if and
only if d’is graphic, where d’is obtained from dby 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 d2-1,…..,d+1-1.
These d
iare the largest elements of dafter (one copy of)
itself,
Note : d2-1,…..,d+1-1need not be the largest numbers
in d’ (see example in previous page)
Graph Theory
99
G’
New added
vertex
d: d
1,d
2,… d
n
d’: d2-1,…..,d+1-1,… d
n
May not be the 
largest numbers

100. 100
Theorem
1.3.31continue
To prove necessity, 3/6
Given a simple graph Grealizing d, we produce
A simple graph G’realizing d’.
Let wbe a vertex of degree in G, and let Sbe a set of 
vertices in Ghaving the “desired degrees” d
2,…..,d
+1.
Graph Theory
100
d: d
1, d
2, …d, d+1,… d
n
S: verticesd
1=
w

101. 101
Theorem
1.3.31
Proof: continue4/6
If N(w)=S, then we delete wto obtain G’.
Graph Theory
101
d: d
1, d
2, …d, d+1,… d
n
Vertices, N(w)=S
i.e. They are connected to w
d
1=
w
Deletewthan we have
d’: d2-1,…..,d+1-1
,… d
n

102. 102
Theorem
1.3.31
Proof: continue5/6
Otherwise,
Some vertex of Sis missing from N(w).
In this case, we modify Gto increase |N(w)S| without
changing any vertex degree.
Since |N(w)S| can increase at most times, repeating this
converts Ginto another graph G*that realizes dand has Sas the
neighborhood of w.
From G*we then delete wto obtain the desired graph G’
realizing d’.
Graph Theory
102
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 changingtheir degree.
d
1=
w

103. 103
Theorem
1.3.31
Proof: continue6/6
To find the modification when N(w)S, we choose xSand
zSso that w z are connected and w x are not.
We want to add wxand delete wz, but we must preserve
vertex degrees. Since d(x)>d(z)and already wis a neighbor of
zbut not x, there must be a vertex yadjacent to xbut not to z.
Now we delete {wz,xy} and add {wx,yz} to increase
|N(w)S| .
Graph Theory
w
z
x
y
This ymust exist.
w
z
x
y

It becomes connected w

104. 104
2-switch 1.3.32
A 2-switchis the replacement of a pair of
edges xyand zwin a simple graph by the
edges yzand wx, given that yzand wxdid
not appear in the graph originally.
Graph Theory
104w x y z y z w x

105. 105
Theorem:If Gand Hare two simple graphs with vertex set V,
then d
G(v)=d
H(v) forevery vVif and only if there is a
sequence of 2-switches that transforms Ginto 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
nthere is at
most one simple graph with d(vi)=d
i.
Hence we can use n=3 as the basis step.
Graph Theory
105

106. 106
Theorem. 1.3.33 (Continue)
Consider n4, and let wbe 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 Gto a graph G*such that N
G*(w)=S,
and some such sequence transforms Hto a graph H*such
that N
H*(w)=S.
Since N
G*(w)=N
H*(w), deleting wleaves simple graphs
G’=G*-wand H’=H*-wwith d
G’(v)=d
H’(v)for every
vertex v.
Graph Theory
106

107. 107
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 toHby transforming G to G*,
then G*to H*, then (in reverse order) the transformation
of Hto H*.
Graph Theory
107

108. 108
Directed Graph and Its edges 1.4.2
A directed graphor digraphGis a triple:
A vertex setV(G),
An edge setE(G), and
A function assigning each edge an ordered pairof vertices.
The first vertex of the ordered pair is the tailof the edge
The second is the head
Together,they are the endpoints.
An edge is said to be fromits tail toits head.
The terms “head” and “tail” come from the arrows used to
draw digraphs.
Graph Theory
108

109. 109
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.
Graph Theory
109

110. 110
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.
Graph Theory
110

111. 111
Loop and multiple edges in directed graph1.4.3
In a graph, a loopis an edge whose endpoints are equal.
Multiple edgesare edges having the same ordered pair of
endpoints.
A digraph is simpleif each ordered pair is the head and tail of
the most one edge; one loop may be present at each vertex.
Graph Theory
111
Loop
Multiple
edges

112. 112
Loop and multiple edges in directed graph1.4.3
In the simple digraph, we write uvfor an edge with
tail uand head v.
If there is an edge form uto v, then vis a successor
of u, and uis a predecessorof v.
We write uvfor “there is an edge from uto v”.
Graph Theory
112
Predecessor
Successor

113. 113
Path and Cycle in Digraph 1.4.6
A digraph is a pathif it is a simple digraph
whose vertices can be linearly ordered so
that there is an edge with tail uand head vif
and only if vimmediately follows uin the
vertex ordering.
A cycleis defined similarly using an
ordering of the vertices on the cycle.
Graph Theory
113

114. 114
Underlying graph 1.4.9
The underlying graphof a digraphD:
the graph Gobtained by treating the edges of Das
unordered pairs;
the vertex set and edges set remain the same, and the
endpoints of an edge are the same in Gas in D,
but in Gthey become an unordered pair.
Graph Theory
114
The underlying GraphA digraph

115. 115
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 Gfor the graph and Dfor the digraph. When
discussing a single digraph, we often use G.
Graph Theory
115

116. 116
Adjacency Matrix and Incidence Matrix
of a Digraph1.4.10
In the adjacency matrixA(G) of a digraph
G, the entry in position i, jis the number of
edges from v
ito v
j.
In the incidence matrixM(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.
Graph Theory
116

117. 117
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.
Graph Theory
117











0000
1010
0101
0100 















10000
11110
01101
00011 w x y z w x y z w x y z a b c d e )(GA G )(GM a b e c d w x y z

118. 118
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.
Graph Theory
118

119. 119
Weakly and strongly connected digraphs
1.4.12
A graph is weakly connectedif its
underlying graph is connected.
A digraph is strongly connectedor strongif
for each ordered pair u,vof vertices, there
is a path from uto v.
Graph Theory
119

120. 120
Eulerian Digraph 1.4.22
An Eulerian trailin digraph (or graph) is a
trail containing all edges.
An Eulerian circuitis a closed trail containing
all edges.
A digraph is Eulerianif it has an Eulerian
circuit.
Graph Theory
120

121. 121
Lemma.If Gis a digraph with 
+
(G)1, then G
contains a cycle. The same conclusion holds
when 
-
(G) 1.1.4.23
Proof.
Let Pbe a maximal path in G, and ube the last vertex
of P.
Since Pcannot be extended, every successor of umust
already be a vertex of P.
Since 
+
(G)1, uhas a successor von P.
The edge uvcompletes a cycle with the portion of P
from vto u.
Graph Theory
121

122. 122
Theorem: A digraph is Eulerianif and only if
d
+
(v)=d
-
(v) for each vertex vand the underlying
graph has at most one nontrivial component.
1.4.24
Graph Theory
122

123. 123
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 nconsecutive digitals are all distinct?
Example: For n=4, (0000111101100101) works.
Graph Theory
123
0000 0001 0011 0111 1111 1110 1101 1011 …
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1

124. 124
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 nconsecutive portions.
If the coding has the property specified above, then the
position of the drum is determined by the string read by the
sensors.
Graph Theory
124

125. 125
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 ato bif the last n-2 entries of
aagree 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.
Graph Theory
125

126. 126
De Bruijn cycles 1.4.25
Graph Theory
126
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 ato bif the last n-2
entries of aagree with the first n-2
entries of b.
Label the edge with the last entry of b.

127. 127
Theorem.The digraph D
nof Application 1.4.25 is
Eulerian, and the edge labels on the edges in any
Eulerian circuit of D
nform a cyclic arrangement in
which the 2
n
consecutive segments of length nare
distinct. 1.4.26
Proof:
We show
first that D
nis Eulerian.
Then the labels on the edges in any Eulerian
circuit of D
nform a cyclic arrangement in
which the 2
n
consecutive segments of length n
are distinct.
Graph Theory
127

128. 128
Theorem.The digraph D
nis 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.
Graph Theory
128
001
101
011
110
111

129. 129
Theorem.The digraph D
nis Eulerian 1.4.26
Proof:2/2
Also, D
nis 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
nsatisfies the hypotheses of Theorem
1.4.24 and is Eulerian.
Graph Theory
129
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

130. 130
Theorem.The labels on the edges in any Eulerian circuit ofD
n
form a cyclic arrangement in which the2
n
consecutive
segments of lengthnare distinct.1.4.26
Proof: 1/4
Let Cbe 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.
Graph Theory
130
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

131. 131
Theorem.The labels on the edges in any Eulerian circuit ofD
n
form a cyclic arrangement in which the2
n
consecutive
segments of lengthnare distinct.1.4.26
Proof: 2/4
The successive earlier labels (looking
backward) must have been a
n-2,…..,a
1in
order.
because we delete the front and shift the reset to
obtain the reset of the name at the head
Graph Theory
131
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

132. 132
Theorem.The labels on the edges in any Eulerian circuit ofD
n
form a cyclic arrangement in which the2
n
consecutive
segments of lengthnare distinct.1.4.26
Proof: 2/4
If Cnext uses an edge with label a
n, then the list
consisting of the nmost recent edge labels at that time
is a
1,…..a
n.
Graph Theory
132
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

133. 133
Theorem.The labels on the edges in any Eulerian circuit of
D
nform a cyclic arrangement in which the 2
n
consecutive
segments of length nare 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
Graph Theory
133
011 0
011 1
Distinct vertex
label
Distinct labels on
out-goingedges

134. 134
Theorem.The labels on the edges in any Eulerian circuit of
D
nform a cyclic arrangement in which the 2
n
consecutive
segments of length nare distinct.1.4.26
Proof: 4/4
We have shown that the 2
n
strings of length nin the
circular arrangement given by the edge labels along C
are distinct.
Graph Theory
134