Fundamental circuit and cut-set

Question

When Finding all the fundamental circuits and cut sets of $K_{3,3}$ and $K_5$ graph ,does planarity have any effect ?

Answer 1

Note that a set of fundamental circuits or cuts is based on the chosen spanning tree. So pick a spanning tree of the given graph, call it $T$. The fundamental cycles are those formed by adding edges to $T$ from $G \setminus T$ such that a cycle is created.

A fundamental cut consists of $E(T) \setminus e$ for a single edge $e$ in $T$. That is, removing an edge from $T$ is a fundamental cut. The fundamental set of cuts consists of all such fundamental cuts for $T$.

Edit: There are $6$ vertices in $K_{3, 3}$, and so a spanning tree has $5$ edges. Let's take $P_{6}$, a path on $6$ vertices, as our spanning tree. Let the first partition have odd numbered vertices, and the second partition have even numbered vertices. So our path is $1-2-3-4-5-6$. So we can add an edges $\{1, 4\}, \{1, 6\}$ to create cycles. There are two edges we can add for each odd vertex. Thus, there are $6$ fundamental cycles in $K_{3, 3}$.

In $K_{5}$, let's take $P_{5}$ as our spanning tree. Each pair of vertices are adjacent in $K_{5}$. So if our path is $1-2-3-4-5$, adding any edge from $K_{5}$ will create a cycle. And so there are $\binom{5}{2} - 4 = 10 - 4 = 6$ edges in $G \setminus P_{5}$ to add, and each will create a different cycle. So there are $6$ fundamental cycles.