Vertex Cover of size k in a tree? What is a polynomial time algorithm for finding a vertex cover of size $k$ in a tree? Would depth first or breadth first search be efficient or is there some other algorithm that finds the vertex cover that takes $n^k$ time rather $2^n$ time?
Hint: Suppose $x$ is a leaf and $y$ is the unique neighbor of $x$. Show that there is always a minimum vertex cover which contains $y$. (Every vertex cover contains either $x$ or $y$; if it contains $x$, then replacing $x$ with $y$ we still get a vertex cover.)