See 2018


This thesis contains many new contributions to the field of Hamiltonian graph theory, a very active mathematical subfield. ‘It is well-known for the Travelling Salesman Problem,’ says Tao Tian. ‘It theoretically states the best route between vertices, or nodes.’

In his work a Hamilton cycle corresponds to traversing the vertices and edges in such a way that all their vertices are visited exactly once, returning to the starting vertex. ‘Solving this problem is of interest in many application fields,’ Tao says. ‘For example in finding the best – low-cost and minimal distance – route in transport.’

 Also another class of Hamiltonian paths is of interest, traversing the graph, terminating at a different vertex.  

‘The existence of Hamilton cycles is also related to early attempts of Peter Guthrie Tait to prove the well-known Four Colour Conjecture (now Four Colour Theorem),’ Tao writes. This states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colours are required to colour the regions of the map, so that no two adjacent regions have the same colour.


‘Professor Hajo Boersma was my promotor at the Formal Methods and Tools (FMT) research group being an expert on graph theories,’ Tao says. ‘Content wise I learnt a lot, and I appreciated the friendly atmosphere at Mesa+. After this one year I will return to China, in order to finish my other PhD phase, on a related subject. Professor L. Xiong will be my promotor then. Now he is a member of the Committee of this PhD research.’


Tao appreciated his stay at Mesa+, learning a lot of the open research atmosphere in Holland. ‘There was always room for saying ‘hello’ and asking for advice, provided you had thought of the right questions,’ he says.

 ‘A lot of academic skills I have learnt here, for example in writing and publishing my work in leading journals and presenting the results to colleagues and at conferences. One day I hope to be a professor in China, or to work as a mathematician at a renowned university.’


With his work, Tao successfully unified and extended several existing results in the field, making connections and further generalizations by Ryjáček’s closure operation and Catlin’s reduction method.

‘Throughout this thesis, we have investigated the existence of Hamilton cycles and Hamilton paths under different types of degree and neighborhood conditions,’ Tao writes. ‘Despite our new contributions the field is very much alive. Many problems and conjectures remain still unsolved.’