144 CHAPTER 2 Discrete Mathematics
(a) Show thatT∗is a spanning tree inG∗.
(b) Conclude that v =eT+ 1 and f =eT∗+ 1, where eT is the
number of edges inT andeT∗ is the number of edges inT∗.
(c) Conclude thateT+eT∗=e(the number of edges inG).
(d) Conclude that v+f = (eT+ 1) + (eT∗+ 1) =e+ 2, thereby
giving another proof of Euler’s theorem.