THE THREE-IN-A-TREE PROBLEM

We show that there is a polynomial time algorithm that, given three vertices of a graph, tests whether there is an induced subgraph that is a tree, containing the three vertices. (Indeed, there is an explicit construction of the cases when there is no such tree.) As a consequence, we show that there is a polynomial time algorithm to test whether a graph contains a "theta" as an induced subgraph (this was an open question of interest) and an alternative way to test whether a graph contains a "pyramid" (a fundamental step in checking whether a graph is perfect).