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


closed as off-topic by ml0105, Grigory M, user7530, user63181, user147263 Dec 23 '14 at 23:08

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – ml0105, Grigory M, user7530, Community, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ No, planarity is irrelevant. Just find them in the usual way. $\endgroup$ – Casteels Dec 23 '14 at 22:05

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.

  • $\begingroup$ Can you tell me the number of fundamental circuits in K5 and K3,3? $\endgroup$ – Priyaranjan Dec 23 '14 at 22:10
  • $\begingroup$ @Priyaranjan I have edited my answer accordingly. $\endgroup$ – ml0105 Dec 23 '14 at 22:19
  • $\begingroup$ Thanks for the solution :) $\endgroup$ – Priyaranjan Dec 23 '14 at 22:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.