Can a chord determine two fundamental circuits in a graph

381 Views Asked by At

I was studying fundamental circuits,fundamental cutsets related theorems,then I came across a question in my mind: Is it possible that a chord with respect to a given spanning tree in a graph determine two fundamental circuit? If so please provide a example.

1

There are 1 best solutions below

1
On

No. If it did, then two non-chord parts of the cycles could be spliced together to form a loop in the tree, which is a contradiction.

In detail: Suppose that $e_1, \ldots, e_k, c$ is a loop, where $c$ is a chord and the $e_i$ are edges in the tree, and that $f_1, \ldots, f_n, c$ is also a cycle, again with the $f_i$ in the tree. Then $s = e_1, \ldots, e_k, f_1, \ldots f_n$ is a cycle all of whose edges are in the tree. The only question is whether it's a nontrivial cycle. Since you've said that $c$ determines two fundamental circuits, I'm assuming you mean that the circuits are distinct, and by "distinct", I'm assuming you mean "don't contain the same edges"; that means that one of the $e_i$ differs from all the $f_j$, so that pairwise cancellations (in which sequences like $a b b^{-1}d$ and "cancelled" to become $ad$ (here $b^{-1}$ indicates the reverse of the edge $b$) ) cannot remove all the edges from the path $s$. So $s$, when reduced to have no hairpins, in a noncontractible cycle in the contractible spanning tree $T$. That's a contradiction.