Math1081 topic 5 notes answers PDF

Preview

Summary

F. Greenhill MATH1081 Discrete Mathematics Graph Theory Loosely speaking, a graph is a set of dots and lines. The dots are called vertices and the lines are called edges. Formally, a graph G consists of A finite set V whose elements are called the vertices of A finite set E whose elements are called...

Description

F. Kuo/T. Britz/D. Chan/D. Trenerry/C. Greenhill

MATH1081 Discrete Mathematics

§5 Graph Theory Loosely speaking, a graph is a set of dots and dot-connecting lines. The dots are called vertices and the lines are called edges . Formally, a graph G consists of A finite set V whose elements are called the vertices of G; A finite set E whose elements are called the edges of G; A function that assigns to each edge e ∈ E an unordered pair of vertices, called the endpoints of e. This function is called the edge-endpoint function. Note that these graphs are not related to graphs of functions. Graphs can be used as mathematical models for networks such roads, airline routes, electrical systems, social networks, biological systems and so on. Graph theory is the study of graphs as mathematical objects. Example. Consider the following graph G with vertices and edges V = {v1 , v2 , v3 , v4 , v5 } and E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 } :

v3 e4

e2 e5 v1

e1

v2

e3

v4 e 6 v5

e7

Edge e1 e2 e3 e4 e5 e6 e7

Endpoints {v1 , v2 } {v2 , v3 } {v2 , v4 } {v3 , v4 } {v3 , v4 } {v4 , v5 } {v5 }

Example. The following diagrams represent the same graph. e1 e1 e4 e1 e3 e3 e3 v1 e4 v1 e4 v1 v2 v3 v2 v3 v3 e2 e2 e2 The edge-endpoint function of this graph is given below: Edge e1 e2 e3 e4

Endpoints {v1 , v2 } {v1 , v2 } {v2 , v3 } {v3 }

If the edge e ∈ E has endpoints v, w ∈ V then we say that the edge e connects the vertices v and w; the edge e is incident with the vertices v and w; the vertices v and w are the endpoints of the edge e; the vertices v and w are adjacent ; the vertices v and w are neighbours . Two edges with the same endpoints are multiple or parallel . A loop is an edge that connects a vertex to itself. The degree of a vertex v, denoted by deg(v), is the number of edges incident with v, counting any loops twice. An isolated vertex is one with degree 0, and a pendant vertex is one with degree 1.

v2

v3

v6 e4

e2 e5 Exercise.

v1

e1

v2

v4 e 6 v5

e3

e7

Vertex v1 v2 v3 v4 v5 v6

Degree 1 3 3 4 3 0

In the diagram, e3 connects vertices v2 and v4 ; v2 and v3 are adjacent/neighbours; e7 is a loop; e4 and e5 are multiple/parallel edges; v1 is a pendant vertex; v6 is an isolated vertex. The Handshaking Theorem. The total degree of a graph is twice the number of edges: X 2|E| = deg(v) . v∈V

Proof.

Each edge has two endpoints and must contribute 2 to the sum of degrees, which is why we count a loop twice.

Example. v3 e4

e2 v1

e1

v2

v6

e5 e3

v4 e 6 v5

e7

2|E| = 2 · 7 = 14 X deg(v) = 1 + 3 + 3 + 4 + 3 + 0 = 14 v∈V

By the Handshaking Theorem, the total degree of a graph must be even and the number of odd vertices must be even.

Example. No graph can have vertex degrees 3,3,3,2,2. Why? 3 + 3 + 3 + 2 + 2 = 13 is odd.

A simple graph is a graph with no loops or parallel edges. Example.

A simple graph

Not a simple graph

Not a simple graph

Note: each vertex in a simple graph on n vertices has degree at most n − 1. Why? Exercise. Prove that no simple graph can have the following vertex degrees: 5,4,3,2,2; A simple graph with 5 vertices has all vertex degrees ≤ 4 4,3,3,1,1. Proof. For a contradiction suppose there is a simple graph G with vertex degrees 4, 3, 3, 1, 1. Label the corresponding vertices a, b, c, d, e. Since deg(a) = 4, vertex a must be adjacent to all the other 4 vertices. This gives all vertices degree 1, fulfilling the requirements of d and e. a e c b d Now there are only two ways to add two edges so that b and c both end up with degree 3, without increasing the degree of a, d or e. Either both b and c are adjacent to a loop, or there is a double edge between them. In either case we contradict the assumption that G is simple.

SOME NAMED GRAPHS 1. The complete graph Kn (n ≥ 1) is a simple graph with n vertices; exactly one edge between each pair of distinct vertices. Hence Kn has C(n, 2) edges.

K1

K2

K3

K4

K5

K6

2. The cyclic graph Cn (n ≥ 3) consists of n vertices v1 , v2 , . . . , vn ; n edges {v1 , v2 }, {v2 , v3 }, . . . , {vn−1 , vn }, {vn , v1 }.

C3

C4

C5

C6

3. The n-cube Qn is the simple graph with vertices for each bit string a1 a2 · · · an of length n, where ai ∈ {0, 1}; an edge between vertices a1 a2 · · · an and b1 b2 · · · bn if and only if aj 6= bj for exactly one j ∈ {1, . . . , n}. ⋆ Two vertices are adjacent if and only if they differ by one bit. 011 01

111

11 010

110 001

00

101

000

10

100

Q2

Q3

BIPARTITE GRAPHS A graph is bipartite iff its vertex set V can be partitioned into subsets V1 , V2 so that every edge has an endpoint in V1 and an endpoint in V2 . In other words, no vertex is adjacent to any vertex in the same subset. Example. Is the following graph bipartite? b c a

d f

e

Yes: let V1 = {a, c, e} and V2 = {b, d, f }; then each edge has a vertex in V1 and a vertex in V2 , as we can see by redrawing the graph, for instance as follows: a b c

f

e

d

Example. Is the cycle C5 bipartite? a e

b c

d

No.

The complete bipartite graph Km,n is the simple bipartite graph with vertex set V1 ∪ V2 , with V1 containing m vertices and V2 containing n vertices; edges between every vertex in V1 and every vertex in V2 . Km,n has m + n vertices and mn edges. Example.

V1

V2 K1,2

K2,2

K3,5

Let G1 and G2 be two graphs with vertex sets V1 and V2 and edge sets E1 and E2 , respectively. Then G1 is a subgraph of G2 , and we write G1 ⊆ G2 , iff V1 ⊆ V2 ; E1 ⊆ E2 ; each edge in G1 has the same endpoints as in G2 . Pictorially, a graph obtained by deleting somes edges and/or vertices is a subgraph. If a vertex is deleted then all edges incident with it are also deleted. Example. G1 ⊆ G2 . a

a

b

c d g

f

c

e h

d

e g

f G1

G2

Let G be a simple graph. The complementary graph G of G is a simple graph with the same vertex set as G; an edge joining two vertices if and only if they are not adjacent in G. Example.

c

d

c

d

a

b

a

b

G

G

Problem Set 5, Problem 10. If a simple graph G has n vertices and m edges, then how many edges does G have? The complement G has n vertices. There are C(n, 2) possible edges in total, and G contains m of them, so G has C(n, 2) − m edges. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Now try Problem Set 5, Questions 1–12.

ADJACENCY MATRIX Let G be a graph with an ordered listing of vertices v1 , v2 , . . . , vn . The adjacency matrix of G is the n × n matrix A = [aij ] with aij = # edges connecting vi and vj . The entries aij depend on the order in which the vertices have been numbered. Changing the vertex order corresponds to permuting rows and columns. The adjacency matrix A is symmetric, i.e., A = AT . Example. v1

v2

v3   0 2 0 A =  2 0 1 0 1 1

v1

v3

v2   0 0 2 A =  0 1 1 2 1 0

Exercise. Is the graph G with adjacency matrix A below simple?   0 1 0 A = 1 0 1  . 0 1 0

Answer. 0’s on the diagonal of A =⇒ G has no loops.

All off-diagonal entries ≤ 1 =⇒ G has no parallel edges. Hence G is simple.

. . . . . . . . . . . . . . . . . . . . . . . . . Now try Problem Set 5, Questions 13 and 14.

PATHS & CIRCUITS A walk in a graph G is an alternating sequence of vertices vi and edges ei in G v0 e1 v1 e2 v2 . . . vn−1 en vn where vi−1 and vi are the endpoints of edge ei for all i. The length of the walk is the number of edges involved (n above). A closed walk is one that starts and ends in the same vertex. In a simple graph, a walk can be specified by stating the vertices alone. Example. e1 v1 e2

e3 v2

v3

e4

v1 e1 v2 e3 v3 e4 v3 is a walk of length 3 from v1 to v3 . v1 e1 v2 e2 v1 is a closed walk of length 2 from v1 to v1 . A path is a walk with no repeated edges. A circuit is a closed walk with no repeated edges. Example. Consider a simple graph v1

v5 v2

v4 v3

v1 v2 v4 v3 v2 is a walk of length 4 from v1 to v2 . It is also a path. v1 v2 v4 v3 v2 v4 v5 is a walk but not a path because edge v2 v4 is repeated. v2 v3 v4 v2 is a circuit.

A path v0 e1 v1 e2 v2 . . . vn−1 en vn is simple iff all the vi are distinct i.e. there are no repeated vertices. A circuit v0 e1 v1 e2 v2 . . . vn−1 en vn is simple iff v1 , . . . , vn are distinct (but v0 = vn of course). Example. v1

e1

v2 e2

e6 v5

e5

v3

e3

e4 e7

v4

v5 e7 v4 e6 v2 e2 v3 e4 v4 e5 v2 is a path of length 5 from v5 to v2 . It is not simple. v1 e1 v2 e2 v3 e4 v4 e7 v5 is a simple path of length 4 from v1 to v5 . v2 e6 v4 e4 v3 e2 v2 is a simple circuit of length 3.

Theorem. Let a and b be vertices in a graph. If there is a walk from a to b, then there is a simple path from a to b. Proof. Suppose that there is at least one walk from a to b. Let W = v0 e1 v1 · · · vn be a walk from a to b with the shortest possible length. Suppose that W is not a simple path. Then some vertex occurs twice, say vi = vj for some i < j . By removing the walk vi ei+1 · · · vj from W , we get the walk v0 e1 v1 · · · ei vi ej+1 vj+1 · · · vn . This is a walk from a to b with shorter length than W . But W had the shortest length, so we have a contradiction. Therefore, W must be a simple path.

Theorem. If A is the adjacency matrix for G with ordered vertices v1 , . . . , vn , then the number of walks of length k from vi to vj in G is given by the entry in the ith row and jth column of Ak .

Example. e1 v1 e2

e3 v2

e4

v3

 0 2 0 A = 2 0 1 0 1 1



4 0 2 A = 0 5 1  2

2 1 2

From A2 we can see that there are 2 walks of length 2 from v1 to v3 , namely v1 e1 v2 e3 v3

and

v1 e2 v2 e3 v3 ;

4 walks of length 2 from v1 to v1 , namely v1 e1 v2 e1 v1 ,

v1 e1 v2 e2 v1 ,

v1 e2 v2 e1 v1 and v1 e2 v2 e2 v1 .

Proof. (of the Theorem) We will use induction: (k) Let aij be the entry in the ith row and jth column of Ak .

(1)

Basis step: aij = aij is the number of edges with endpoints vi and vj ; (1) that is, a ij is the number of walks of length 1 from vi to vj . Hence, the theorem is true for k = 1. Assume that the theorem is true for some k ≥ 1. Then, since Ak+1 = Ak A, n n X X (k) (1) (k+1) (# of walks of length k from vi to vl ) = ail alj = aij l=1

l=1

× (# of walks of length 1 from vl to vj ) n X = (# of walks of length k + 1 from vi to vj via vl ) l=1

= # of walks of length k + 1 from vi to vj

Thus, the theorem is true for k +1, so by induction, the theorem is true for all k .

. . . . . . . . . . . . . . . . . . . . . . . . . Now try Problem Set 5, Questions 19 and 20.

CONNECTIVITY Vertices a, b of a graph G are connected in G iff there is a walk from a to b. A graph G is connected iff every pair of distinct vertices is connected in G. Let G be a graph with vertex set V . The relation ∼ on V defined by vi ∼ vj

if and only if vi is connected to vj in G

is an equivalence relation. The equivalence classes of this relation are the connected components of G. Two vertices are in the same connected component if and only if they are connected in G.

Example. The graph G1 below is connected, but G2 is disconnected. The 3 connected components of G2 have been shaded.

G1

G2

Let G be a graph with vertices v1 , . . . , vn and adjacency matrix A. Let C = I + A + A2 + · · · + An−1 . Then G is connected if and only if C has no zero entries.

Proof. Firstly, note that every entry of I, A, A2 , . . . , An−1 is a nonnegative integer. If G is connected then any two vertices vi , vj are joined by some walk of length k ≤ n − 1. Hence the (i, j) entry of Ak is nonzero, and so the (i, j) entry of C is nonzero. Conversely, if cij = 6 0 then some power Ak has a nonzero (i, j) entry, which means that there is a walk (of length k) from vi to vj .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Now try Problem Set 5, Question 18. EULER & HAMILTON PATHS & CIRCUITS Let G be a graph. An Euler path in G is a path that includes every edge of G exactly once. A Hamiltonian path in G is a simple path that includes every vertex of G exactly once. An Eulerian circuit in G is a circuit that includes every edge of G exactly once. A Hamiltonian circuit in G is a simple circuit which includes every vertex of G exactly once (counting the start-vertex once).

Example.

a

b d

c f

e g

cf dacdgebde is an Euler path; acf dbeg is a Hamilton path. Example. A network of roads is to be snow-ploughed. An Euler circuit will ensure that all roads get ploughed without going over a road already cleared. Example. Similarly for a postman delivering mail. Example. A salesperson wants to visit some towns using a network of roads. If the salesperson follows a Hamilton circuit then they will visit each town exactly once, and will finish up where they started. Theorem. Let G be a connected graph. An Euler circuit exists if and only if G has even vertex degrees i.e. there are no vertices with odd degree.

Proof. (=⇒) Suppose that an Euler circuit C exists in G. Each time C passes through a vertex v, it uses up 2 distinct edges, one on the way in and one on the way out. Every edge is used exactly once, so deg(v) is twice the number of times C passes through v. Therefore, deg(v) is even.

(⇐=) Conversely, suppose that G has no vertex of odd degree. We need

Lemma Let G′ be a graph with even vertex degrees. Then any path v0 e1 v1 . . . e n vn with v0 6= vn can be extended to a circuit v0 e1 v1 . . . en vn en+1 . . . vm with vm = v0 .

Proof of Lemma: The path v0 e1 v1 . . . en vn uses up an odd number of edges incident on vn . But deg(vn ) even, so there must be an unused edge en+1 adjacent to vn . If en+1 = vn v0 then this gives a circuit. Otherwise, we have a longer path v0 e1 v1 . . . en vn en+1 vn+1. Continue inductively until a circuit is found.

We now return to the proof of (⇐=) and use the following algorithm to produce an Euler circuit C : Euler Circuit Choose a vertex v0 in G. Start with length 0 circuit C := v0 . while there exists an edge not in C do choose a vertex v ∈ C and an edge e ∈ / C that is incident with v; ′ choose a circuit C starting and finishing at v that contains e, but does not contain any edge in C ; Replace one of the appearances of v in C by C ′ ; end do The vertex v and edge e exists because G is connected. To see that the circuit C ′ exists, apply the Lemma to the graph obtained from G by deleting all edges of C . The algorithm terminates because G has only finitely many edges, and every step adds at least one edge to C . By construction, C is an Euler circuit. This proves the theorem.

Example. Apply Euler Circuit to construct an Euler circuit below: f

a

d

c

b

e

g First note that the degree of each vertex is even. If we initially take v0 := a then at the first step of the algorithm, one possible choice for C ′ is as follows: f 4 3

v=a

b

C = C′ 2

1

g At the second step, we may take v := g and choose C ′ as follows: f f 2

8

3

3

c

a

d

4

6

5

c

b

4 1

7

1

d 2

v=g

g

C C′ At the third step, we must take v := d, and can choose C ′ as follows: f 11

6 10

a

1

e

d

9

2

g C

We now have an Euler circuit C .

C

3

e 5

8

1

′

d

c

b

2

3

7

4

Theorem. Let G be a connected graph. An Euler path which is not a circuit exists if and only if G has exactly two vertices of odd degree. Proof. (=⇒) Assume that G has an Euler path v0 e1 v1 . . . en vn (with v0 6= vn ), and consider the graph G′ formed from G by adding a new edge e′ that connects v0 and vn . Since v0 e1 v1 . . . en vn e′ v0 is an Euler circuit in G′ , we know that each vertex in G′ has even degree. Hence, G has exactly two vertices of odd degree, namely, v0 and vn . (⇐=) Conversely, suppose that G has exactly two vertices of odd degree, say a and b. We form G′ by connecting a and b with a new edge e′ , so that every vertex in G′ has even degree. Hence, G′ has an Euler circuit. Removing the new edge e′ from G′ again gives an Euler path for G. The K¨ onigsberg Bridge Problem. In the 18 century, Kaliningrad in the Russian Republic was called K¨onigsberg, and was part of Prussia. At that time, seven bridges connected the four different parts of the town, as depicted in the diagram below. a c

b d

The question arose as to whether it was possible to start from one part of the town, cross every bridge exactly once, and return to the starting point.

In the first ever paper on graph theory, in 1736, Leonhard Euler explained why this could not be done and proved the theorems about when an Euler circuit or Euler path exist. We now know that the problem is equivalent to finding an Euler circuit in the following graph. a c

b d

Here, deg(a) = 3, deg(b) = 5, deg(c) = 3, and deg(d) = 3, so there are 4 vertices with odd degree, and hence no Euler circuit (or path) exists.

No simple necessary and sufficient criteria are known that determine whether a graph has a Hamilton circuit or path. Note that a graph with a vertex of degree 1 cannot have a Hamilton circuit. If a graph G has a Hamilton circuit, then the circuit must include all edges incident with vertices of degree 2. A Hamilton path or circuit uses at most 2 edges incident with any one vertex. Example. The following graphs have no Hamilton circuits: d

g

c e a

a

b

f e

c b

d

To see that the second graph has no Hamilton circuit, note that b, d, f, g each have degree 2, so any Hamilton circuit would have to use all edges incident with these vertices, including the four edges incident with c.

Theorem. (Dirac 1952) Let G be a connected and simple graph with n ≥ 3 vertices, such that each vertex has degree at least n/2. Then G has a Hamilton circuit. Example. The complete graph Kn is connected and simple, and has n vertices. Each vertex is adjacent to every other vertex, ...