MAST30011 Graph Theory 2021
ASSIGNMENT 2
Due 13:00pm Friday 21 May 2021
1. Let G be the bipartite graph below and let M = {v1w1, v3w3, v4w4} be the matching
in G as shown in green colour.
(a) Grow a maximal alternating tree in G with respect to M with root v2.
(b) Use this tree to obtain a matching in G with four edges.
(c) Is it possible to find an augmenting path with respect to this new matching?
If so give such a path and augment along it to obtain a matching with five
edges. Otherwise give reasons why such an augmenting path does not exist.
v1
v2
v3
v4
v5
w1
w2
w3
w4
w5
Figure 1: Question 1
2. Let M be a matching in a graph G, and let S be the set of vertices matched by
M . Prove that there exists a maximum matching M∗ in G such that all vertices
in S are matched by M∗.
3. Let N be the following network with source x and sink y as shown below. The arc
capacities are shown beside each arc, and an initial flow is given in parentheses.
(a) Starting from the given initial flow, apply the labelling algorithm to find a
maximum flow in N . Show every stage of the algorithm, and in each iteration
of the algorithm label all vertices that can be labelled and show how you
obtain the labels of such vertices. State explicitly the value of the maximum
flow found.
(b) Give explicitly the minimum cut in N obtained from your results in (a).
1
aed
6 (4)
b
x
y
c
3 (3)
4 (3)
3 (1)
4 (1)
2 (1)
4 (0)
1 (1)
3 (0) 5 (0)
2 (1)
Figure 2: Question 3
4. Recall that a nontrivial graph H is called k-connected if p(x, y) ≥ k for every pair
of distinct vertices x, y of H. Using this definition, prove that for any `-connected
graph G and any edge e of G, where ` ≥ 2, the edge-deletion subgraph G−e (which
is obtained from G by deleting e) is (`− 1)-connected.
5. Let H be a spanning subgraph of a graph G. Which of the following statements
are true? And which of them are false? For a true statement, briefly justify why
it is true; for a false statement, give a counterexample to show it is false.
(a) If H is Eulerian, then G is Eulerian.
(b) If H is Hamiltonian, then G is Hamiltonian.
(c) If H is tough, then G is tough.
(d) If H is not tough, then G is not tough.
2
6. (a) Let G be the following plane pseudograph. Draw the dual of G. Give the
degree of each face of G. (You may need to label the faces of G to facilitate
your solution.)
e1
e4
e3
e2
e6 e5
e7 e9
e8
Figure 3: Question 6
(b) Let Gn be the simple graph with vertex set {v1, v2, . . . , vn} and edge set {vivj :
1 ≤ i, j ≤ n, 1 ≤ |i− j| ≤ 3}, where n ≥ 3. By induction on n, prove that Gn
is a maximal planar graph.
3

欢迎咨询51作业君