Investigating Spanning Trees with Degree Constraints

📄 Project Abstract

This project looks, in depth, at the complexity of spanning trees with inner vertex degree constraints. The project attempts to address the problem: Given a graph G, does G contain a spanning tree with inner vertex degrees equal to k? In this project I aim firstly to give the reader an introduction to the subject of Graph Theory. Secondly, the project will cover the theory of NP-completeness and give the reader an overview of the subject. Thirdly, I will go on to prove that the problem described above is NPcomplete. Finally, I will investigate the boundary between the inner vertices constraints, 2 £ d(u) £ n -1 for a spanning tree, and try to establish a bound on where the problem goes from being able to be solved in polynomial time to being NP-complete.