Let G be a graph with at least 8 vertices of odd degree. Prove that G cannot be decomposed into three paths.
I have an intuitive idea using strong induction on length but cannot seem to flesh it out.