MAST30011 Graph Theory 2021
ASSIGNMENT 1
Due 13:00pm Friday 16 April 2021
1. In the following graph,
(a) give an example of a longest trail,
(b) give an example of a longest cycle,
(c) give an example of a longest path, and
(d) list all induced subgraphs which are paths of length 4.
a b
c
def
h
2. Two of the following graphs F , G and H are isomorphic to each other. For the two
graphs which are isomorphic, give an isomorphism between them and prove that
it is indeed an isomorphism. For the other graph, show that it is not isomorphic
to the two which are isomorphic.






























3. Prove that if G is a graph with no cycles of even length, then every cycle in G is
an induced subgraph of G.
4. Let G be the following weighted graph, where the number next to each edge is the
weight of the edge.
1
ax d
bh
1
5
9
4
2
4
1
7
c
2
y
z
1
6
Apply Dijkstra’s algorithm to find the distance from a to all other vertices of G.
State what the labels of vertices are when each new vertex is chosen to be added
to the set S. Finally, draw a tree determining shortest paths from a to all other
vertices of G.
5. Suppose that G ∼= G and that n = |V (G)| = 4k + 1 for some integer k ≥ 1
(where G is the complement of G). Suppose that the degree sequence of G is
d1 ≥ d2 ≥ · · · ≥ dn.
(a) Prove that di + dn−i+1 = n− 1 for each i = 1, 2, . . . , n.
(b) Use (a) to prove that G has at least one vertex with degree (n− 1)/2.
6. Use the original version of Kruskal’s algorithm to find a minimum spanning tree of
the following weighted graph. List the edges of the minimum spanning tree found
in the order the algorithm adds them to the tree, and compute the weight of this
minimum spanning tree.
a b c
d
e f
g
1 4
13 5 6 7
11
5
86
13
1
2




























































































学霸联盟