DMB - Unit 6

MAAB16 Discrete Mathematics B
Unit 6: More Graph Theory

References

[Biggs] sections 17.1, 17.2, 17.3, 17.4, 17.5

Introduction

In this unit we shall study edge-colourings of graphs and how they can be used to extend Latin Rectangles to become Latin Squares. After this we study bipartite graphs and in particular matchings in bipartite graphs. Matchings can be used to solve problems like finding and optimal assignment of tasks to a work force and are thus very useful for an array of practical problems. We introduce and prove an algorithms for creating a complete matching in a bipartite graph, if it exists. If a complete matching does not exist, our algorithm gives a maximum size matching.

Reading guidelines

Relations between 2 sets and bipartite graphs

Section 17.1 starts by defining what is meant by a relation between two sets. Basically it is a subset of XY. Note that a function f: XY is a relation between X and Y. However, not all relations between X and Y are functions.

Relations between sets X and Y can be represented by bipartite graphs on the vertex set XY where an edge between x X and y Y means x is related to y.

Example A relation between X={1,2,3} and Y={a,b,c} which is not a function

A relation between X={1,2,3} and Y={a,b,c} which is a function

Because we are interested in relations between two sets, we study bipartite graphs.
The first thing to notice is that all edges in a bipartite graph on vertex set XY go between X and Y and so the sum of degrees of vertices in each part is the number of edges in the graph. This is the content of Theorem 17.1.

The section ends with an example about regular bipartite graphs. This example is important. Read it carefully! Then verify it on the following example.

Example Here X is a set of 4 people {A,B,C,D} and Y is a set of 4 jobs {1,2,3,4} where each person is qualified to do precisely 2 jobs and each job can be done by precisely 2 people.

Verify the second claim of the example in [Biggs] p. 211 that

Every person can do at least one job
Every pair of persons (check for all 6 possible pairs!) can do at least 2 of the jobs
Every set of 3 persons (check for all 4 possible 3-sets!) can do at least 3 of the jobs
Every set of 4 persons can do at least 4 of the jobs

Recommended revision exercises are Exercises 17.1.1, 17.1.2, 17.1.3.

Edge colourings of graphs

Sections 17.2 and 17.3 are about edge colourings of graphs. An m-edge colouring of a graph is a colouring of the edges of the graph with m colours in such a way that no two edges which meet at a vertex have the same colour. As with vertex colourings, we are interested in the smallest number of colours needed in order to colour a graph. This is what was called the chromatic index of the graph on Discrete Maths A (MAAA25).

All the edges meeting at a vertex in the graph must have separate colours, so if the maximum degree of the graph is K, then we need at least k colours to edge-colour the graph.

Example
To edge-colour the cycle graph C₄ we need at least two colours as its maximum degree is 2. In this case two colours actually suffice. Here is a 2-colouring of the edges of C₄

Now do exercises 17.2.1 and 17.2.3.

In general if G is a graph with maximum degree K, K colours is not sufficient in order to edge-colour the graph. The simplest examples that show this are the odd-length cycle graphs. You need three colours to edge-colour an odd cycle:

Example
To edge-colour the cycle graph C₃ we need at least two colours as its maximum degree is 2. In this case two colours are not enough though. You need 3 colours in order to edge-colour C₃:

To edge-colour the cycle graph C₅ we need at least two colours as its maximum degree is 2. In this case two colours are not enough though. You need 3 colours in order to edge-colour C₅:

However, when the graph is bipartite and of maximum degree K, then K colours suffice. This is the content of Theorem 17.2.

The proof of theorem 17.2 relies heavily on the graph being bipartite. Otherwise it is an induction on the number of edges in the graph. The induction step creates a colouring of a graph G on m+1 edges with maximum degree K like e.g.

by first removing one edge xy and then using the induction hypothesis to K-colour the edges of the remaining graph.

Then he puts the edge xy back and needs to find a colour for it. Both x and y have degree

K-1 in the graph G-{xy}, so at both these a maximum of K-1 colours are used. If the same colour is missing at both vertices then we can just colour xy in that colour and we are done. Otherwise we have two different colours missing, red and blue say like in our example. The idea is now to change the colouring in such a way that the same colour is missing at x and y. We do that by creating a maximum alternating path of red and blue edges starting at x (if x has a blue edge missing and y a red one).

We then swap red and blue along the alternating path found.

All other edges in the graph are to have the same colour as they had in G-{xy}.

This allows us to colour xy with the colour blue, which is now missing at both x and y.

Now do Exercise 17.2.4.

Edge colourings and Latin Squares

Section 17.3 starts by explaining that an n-colouring of the edges of the complete bipartite graph. K_n,n on vertex set X Y corresponds to a Latin Square of order n. There are three ways in which you can interprete this. Biggs uses two of them:

You can let the triple (row r, column c, symbol s in cell (r,c)) of the Latin Square correspond to (x X, y Y,the colour of xy). Here the Latin Square would correspond to the following edge-coloured K_3,3, where (1,2,3) are the colours (red, blue, green):
However, you can also take what Biggs calls a twisted view and let the triple (symbol s, column c, the row r for which cell(r,c) has the symbol s) correspond to (x X, y Y,the colour of xy). Here the Latin Square would correspond to the following edge-coloured K_3,3, where (r1,r2,r3) are the colours (red, blue, green):

In Theorem 17.3.1 Biggs then proves that any m

n Latin rectangle can be completed to a Latin Square by creating a colouring of the corresponding K_n,n and reversing the above procedure. In Theorem 17.3.2 he gives a necessary and sufficient condition for an m

p Latin rectangle to be completed to a n

n Latin Square. Solve also Exercise 17.3.1 before going on to the next chapter.

Matchings

Sections 17.4 and 17.5 are about matchings. A matching is a set of edges in a (bipartite) graph on vertex set X Y such that none of them have a vertex in common with any of the others. The size of a matching is the number of edges in it. E.g. M={A2,B3,C4} is a matching (of size |M|=3) in the graph

A complete matching is a matching saturating X. The matching M={A2,B3,C4} is not complete as the vertex D

X is not matched.

Not every bipartite graph has a complete matching. A necessary condition is that every set of n vertices in X has at least n neighbours in Y, as by the pigeonhole principle there is no way of matching n vertices to n-1 or less vertices without 'repeating' a vertex. It is a remarkable fact that this necessary condition is also sufficient, i.e. that if every set of n vertices in X has at least n neighbours in Y for n=1,2,3,...,|X|, then a complete matching exists. The condition is known as Hall's condition for the existing of a complete matching. Biggs proves in Theorem 17.4 that the complete matching exists provided that Hall's condition is satisfied.

Example
We checked at the end of our treatment of section 17.1 that Hall's condition holds in the graph

i.e. we checked that every 1-set of X has a neighbour in Y, That every one of the 6 2-subsets of X has at least 2 neighbours in Y, that every one of the 4 3-subsets of X has at least 3 neighbours in Y and that X has at least 4 neighbours in Y. Hence the graph has a complete matching.

The way to find the complete matching is by

starting with any matching M (one edge will do, but it is more efficient to start with a larger one, if you can see one!). E.g. in our graph above we saw that M={A2,B3,C4} is a matching.
Next find an unmatched vertex x in X. E.g. D in our graph
Using BFS-search to grow the tree of M-alternating paths starting with the unmatched vertex as the root. In our example the tree is
In the proof of Theorem 17.4 it is shown that Hall's condition assures that the tree will contain an unmatched vertex y of Y as a leaf. In our example the vertex 1 is such an unmatched vertex.
The alternating path from x to y can be used to augment M to a matching containing one more edge than M itself. In our example the augmenting path is D3B1
Create a new matching by first taking the thin edges in the augmenting path (i.e. the ones not in M) and then add the edges of M not having any vertices in common with these. In our case the M-unused edges in the path are D3 and B1. To these we add the two edges A2 and C4 from M. This yields the complete matching M₁={A2,B1,C4,D3} Recommended exercises are Exercise 17.4.1, 17.4.2.

Maximum matchings
A matching M is a maximum matching in a bipartite graph G if no other matching of G has more edges. When a complete matching of G exists it is obviously maximal. If no complete matching exists because Hall's condition is not satisfied, then the question arises as to how large a matching the graph has. Biggs answers this question in Theorem 17.5.1.

Biggs then goes on to extend the algorithm we used to find a complete matching above to find a maximum matching in any bipartite graph. The basis of the proof that the algorithm works is Theorem 17.5.2 showing that if M is a non-maximal matching in a bipartite graph G, then G contains at least one of the M-alternating paths rooted at an unmatched vertex and ending in an unmatched vertex which can be used to create a matching M₁ with one more edge. Hence we can just start at any matching and augment it by a number of edges, one at a time, until no augmenting M-alternating path can be found. We then know we have a maximum matching.
Example
Let us find a maximum matching in the bipartite graph G:
with X={A,B,C,D,E} and Y={1,2,3,4,5}, starting from the matching M₀={B2,C3,E5}

First augmentation attempt
1. There are unmatched vertices in X, e.g A.
2. We grow the M₀-alternating BFS-tree from A: There are two possible augmenting paths here. One is A2B1 (the other is A2B4).
3. Augment the matching by the 'thin' edges of the path, i.e. the new larger matching is M₁={A2,B1,C3,E5}
Second augmentation attempt
1. There is still an unmatched vertx in X, namely D.
2. We grow the M₁-alternating BFS-tree from D: No unmatched vertex from Y is found at the leaf of this tree. Hence the matching M₁ cannot be augmented, i.e. it is a maximum matching.
3. To prove that this graph has no complete matching witout the second iteration attempt, let S={A,C,D} i.e. S are the vertices from X in the M₁-alternating BFS-tree above. Then the neighbours of S in G are J(S)={2,3}. Hence Hall's condition is not satisfied, so the graph has no complete matching and thus the matching of size 4 we have found must be maximal.
  
  Solve also Exercise 17.5.1.
  
  Assignment 6
  1. Use augmenting paths to find a maximum matching in the bipartite graph G with the following adjacency list, starting from the matching M₀={A1,B5,C7,D2}. Give a short description of the steps in your algorithm.
  2. Show that the matching you found in 1. is a maximum matching.

MAAB16 Discrete Mathematics B Unit 6: More Graph Theory