Can anyone provide, or direct me to a formalized version of Cauchy's proof that for any convex polyhedron with $F$ faces, $E$ edges and $V$ vertices that $F - E + V = 2$. I am willing to accept the polyhedron can be turned into a graph via stereographic projection, and that the triangulation process will be successful. What I have trouble with is why this strategy of removing triangles will always result in a single isolated triangle:
Remove all triangles which share exactly two edges and three vertices with the boundary.
Choose a triangle which shares exactly two vertices and an edge with the boundary.
Repeat steps 1 and 2.
Specifically why can we never 'split' the boundary of our graph into two disconnected polygons in this way?
Yes, it is possible to split the graph into two disconnected parts. Simply decide not to do that.
It may be easier, instead of thinking of decomposing an existing graph, to think of it as building the desired graph up from a single triangle by adding edges/loops/vertices one by one. Then there's no risk of ending with an invalid graph along the way.