The university of sydney math2969/2069

The University of Sydney MATH2969/2069

Graph Theory 1.

Tutorial 2 (Week 9)

2008

Show that the graph on the left is Hamiltonian, but that the other two are not.

Solution. To show that the graph is Hamiltonian, simply find a Hamiltonian cycle. (That is, a cycle which passes through every vertex exactly once.) Unfortunately, finding such a cycle may be tricky, even with so few vertices and edges. It may help to note that exactly two of the edges incident to the central vertex must be used (else this central vertex would not be used exactly once, contrary to requirement). Try assuming that, with the labelling shown, [k, h] and [k, i] are used, and [k, f ], [k, g], [k, j] are not. Then, since f , g, j are to be used, edges [e, f ], [f, b], [a, g], [g, c], [a, j], [j, d] must all be used. (See diagram above right.) With this start, it is not hard to complete a Hamiltonian cycle. An example is shown in the second diagram:

a e j k d i a e j k d i h c f g b h c f g b

The vertices of the second graph can be coloured, each black or white, in such a way that each edge joins a black vertex to a white vertex (eg., as shown in the diagram). Any path using all vertices would then have to alternate between black and white vertices, eg.: v1 = black, v2 = white, v3 = black, v4 = white, . . . , v13 = black (7 blacks and 6 whites), but this last vertex could not be adjacent with the first to complete the cycle, both having the same colour. Hence no Hamiltonian cycle exists.

2 In the third graph, there is an outer pentagon (5 sided figure) of 5 vertices, an innermost pentagon of 5 vertices, and an in-between decagon (10 sided figure) of 10 vertices. On the decagon, 5 of the vertices are of degree 2, which means that in any Hamiltonian cycle all 10 edges of this decagon must be used. (For a path to go through a vertex of degree 2, both incident edges must be used.) Since each vertex must be used only once, this means that none of the edges directed radially outwards