I'm reading Richard J. Trudeau's book "Introduction to Graph Theory",
after defining polygonal
Definition 24. A graph is polygonal is it is planar, connected, and
has the property that every edge borders on two different faces.
from page 102 it prove Euler's formula $v+f-e=2$, starting by
Theorem 8. If $G$ is polygonal then $v+f-e=2$.
Proof…
Now let $G$ be
an arbitrary polygonal graph having $k + 1$ faces. Remove some of the
edges and vertices bordering the infinite face of $G$ to produce a new
polygonal graph $H$ having one less face than $G$, so $H$ has $k$ faces.…
Now think. Whenever edges and vertices are removed from a polygonal
graph in order to produce another polygonal graph having one less
face,
the number of vertices removed is one less than the number of edges removed.
I'm a bit suspicious here: for "the number of vertices removed is one less than the number of edges removed" , shouldn't it need some proof? For example, the removing looks only to erase a path graph, i.e. some $P_n$, but, does this need some proof?
Pls enlighten me.
Best Answer
The author is being at best informal; at worst, one could say "sloppy".
For instance, if $G$ is the graph consisting of two disjoint triangles, then there are three polygonal faces --- two triangles, and one infinite face. If we want to reduce to one triangle, we need to remove both three edges AND three vertices, so the vertex count is NOT one less than the edge-count.
Presumably the author wants to include the hypothesis that the graph $G$ is connected, and maybe that's part of the definition of "polygonal graph." But the example I gave shows that the "Now think..." paragraph depends intimately on the connectedness, but makes no mention of it (and also doesn't show that such a removal preserves connectedness). Sure, it's true. But true things can be hard to prove correctly (witness the Jordan Curve Theorem!), and the quoted text doesn't seem to be doing that hard work in this case.