3
$\begingroup$

Let $G$ be a plane graph, and $G^*$ its dual. Among the $k$ partitions of the nodes of $G$, I'll call the connected k-partitions those such that each block of nodes of the partition induces a connected subgraph of $G$.

It is well known that the connected 2-partitions of the vertices $G$ are dual to the simple cycles of $G^*$. (The duality is by sending the partition to the cut edges of that partition. This is also called the bond / simple cycle duality.)

I believe I have a proof that the connected $k$-partitions of the vertices of $G$ are dual to the set of subgraphs $K$ of $G^*$ with

  • $H_1(K)$ is of rank $k - 1$
  • Each connected component $K$ is $2$ edge connected.

Again, the duality is by sending a partition to the cut edges in that partition. In the other direction, it comes by taking the connected components of $G$ after removing the edges crossing the subgraph $K$.

I use this result in the course of some other proof, and I'm looking for a reference for it (as this seems like the kind of thing that is either wrong, or well known).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.