Here is a proof of the following statement:
Let $T$ be a spanning tree of a connected plane multigraph $G$ and $T^*$ be a subgraph of $G^*$ whose edges correspond to the edges of $G$ not in $T$. Then $T^*$ is a spanning tree of $G^*$.
I am curious about two parts:
First- they did not prove that $T^{*}$ is connected. The proof seems to be a simple and short, but I cannot find the essence of it. Here is another proof containing that part, but as mentioned in the question, it is too hard to understand.
Second- what can we do about the opposite side?They proved 'If $T$ is a spanning tree of $G$ and $T^*$ is constructed in such a way, then $T^*$ is a spanning tree of $G^*$. But can we ensure 'If such constructed $T^*$ is a spanning tree of $G^*$, then $T$ is a spanning tree of $G$.'?
I guess that using 'the dual of a dual graph of connected plane graph is itself' makes it obvious, but I am not clear yet. Could you help me? Thanks.
Best Answer
$E(T^*) = V(T^*)-1$ + acyclicity implies connectedness, this is a standard result for trees. In fact, the three following definitions are equivalent :
$T^*$ is connected and acyclic
$T^*$ is connected and have $V(T^*)-1$ edges
$T^*$ is acyclic and have $V(T^*)-1$ edges
In fact, you just need to of the three properties to have a tree.
The proof of connectedness here is very similar to the acyclicity, if $T^*$ has more than one component, we can find a cycle around that component, which gives a cycle in $T$ (Hence the contradiction).
This is true, except that $T^*$ is not the classic dual of $T$. There is a duality between $T$ and $T^*$ relatively to $G$ and $G^*$, but we need to prove it. This is relatively easy: The edges of the dual of $T^*$ are the edges of $G$, except those corresponding to an edge of $T^*$. As the edges of $T^*$ correspond to the edges of $G$ not in $T$, the remaining edges must be only the ones in $T$.