Please ensure that your name and student number appear on the assignment, which must be submitted in a folder.
1. Decide whether the following two graphs are isomorphic to each other.
If they are isomorphic give an explicit isomorphism.

2. A planar graph is selfdual if it is isomorphic to its dual. (a) Show that if a planar graph G on n vertices and e edges is selfdual, then e = 2n2. (Hint: use Euler's formula, n + f  e = 2.) (b) For each n ≥ 4, find a selfdual planar graph. 
3. Show that if G is 2connected, then for every three vertices a, b, and x, there is a path from a to b containing x. (Hint: add a new vertex y, joined to a and b.) 
4. Let G have n vertices. Show that it is impossible for G to have n distinct degrees. Find all graphs with exactly n1 distinct degrees. (No loops or multiple edges.) 
5. Let G have degree sequence D = (d_{1}, d_{2}, ..., d_{n}), where d_{1} ≥ d_{2} ≥ ... ≥ d_{n}. Show that if d_{n} ≥ (n1)/2, then G is connected. Is this also true if d_{n} ≥ (n2)/2? Explain. 
6. Let G be a bipartite simple graph on n vertices with bipartition (X,Y). Let d_{x} be the minimum degree among the vertices of X, and d_{y} be the minimum degree among the vertices of Y. Show that if d_{x} + d_{y} > n/2, then G is connected, where d_{x}, d_{y} > 0. If d_{x} + d_{y} = n/2, is the conclusion still true? Explain. 
7. Find a TK_{3,3} and a TK_{5} in the graph shown.

8. Find a maximum flow by hand in the network shown. Prove your flow is maximum by illustrating a
minimum edgecut K such that the value of f = capacity of K.

9. A Hamilton cycle in G is a cycle that contains every vertex. A Hamilton path in G is a path that contains every vertex. We are given that HamCycle is NPcomplete. Show that HamPath is also NPcomplete. (Hint: Given a graph G in which we want to find a Ham cycle. Show how to transform G into a graph H, such that a Ham path in H will give a Ham cycle in G.) 
Questions 10, 11, 12 are for students in 7750 only 
10. Let G be a graph with minimum degree at least 3, with a separating set {u,v}. Let H_{1}, H_{2}, ..., H_{k} be the connected components of G{u,v}. Let K_{i} be the graph induced by V(H_{i}) U {u,v}. Show that G is planar iff each K_{i} is planar. 
11. Consider the following network N with flow f indicated in square brackets. Edges with no flow
indicated have zero flow. A breadthfirst search of N will construct the subnetwork of all shortest,
unsaturated paths in N, if it is allowed to continue searching after t is first encountered. This subnetwork is called the auxiliary network, Aux(N,f). A forward edge uv of N with positive residual
capacity is replaced by a forward edge uv with capacity cap(uv)f(uv) in the auxiliary network.
A backward edge uv of N with positive flow is replaced by a forward edge uv with capacity f(uv) in
Aux(N,f). Construct the auxiliary network for the graph shown. Find a max flow in Aux(N,f), and
modify f in N accordingly. Finally, construct a new auxiliary network for N, based on the new flow.

12. Show that if G is connected on n vertices, and n>2δ, where δ is the minimum degree of G,
then G contains a path of length at least 2δ. (Hint: consider the endpoints of a longest path.) 
1. Program the HopcroftTarjan algorithm to find the blocks and cutvertices of a graph.
Print out a list
of cutvertices, and for each block, print out the
edges in the block. Be sure to start the DFSearch
sometimes from a cutvertex, and
sometimes not from a cutvertex.
Text files containing the adjacency lists of the input graphs are available here: graph 1, graph 2 and graph 3.
This means that:
The end of the lists is marked with 0.
Graphs in this format can be very easily input with a pair of nested loops.
Notice that an edge uv occurs only once in the input file,
either with u or v, but not with both.
However, the adjacency
lists must be constructed so that uv appears twice, once for each endpoint.