Q: Prove that if a graph $G$ has $n \geq 2$ vertices, and the sum of the degrees of 2 different vertices is at least $n-2$ (for any 2 different vertices), then the graph has 2 disjoint simple paths, that their union builds the graph $G$ ('covers its vertices') . (The path can be of length $0$ meaning it contains only $1$ vertex)
I am so lost in this proof, I did not even know how to start, I guessed it is about trees, maybe I need to find 2 trees $T_1 ,T_2$ such that $T_1 \cup T_2 = G$ ? How does the information that $ \text{deg}_G(v) + \text{deg}_G(w) \geq n-2 $ for each $v,w \in V(G) ~~ \text{and} ~~ v \neq w$ help us?
Thank you for helping!
Add to $G$ two adjacent vertices, each adjacent to each vertex of $G$. Since the extended graph has $n+2\ge 4$ vertices and sums of degrees of any two of them is at least $n+2$, by Ore’s theorem it has a Hamiltonian cycle. When we remove from it the added vertices, we obtain two (or even one) paths which span $G$.