Adding $k$ edges in a forest creates how many cycles?

53 Views Asked by At

Let $G = (V(G),X)$ be a forest. Let $F$ a edge set such ends of each edge of $F$ are connected in $G$. Is true that to add the edges of $F$ create exactly $|F|$ cycles?

How can I argument this?

1

There are 1 best solutions below

0
On BEST ANSWER

I think this is not true. Consider the tree

    a
  / |  \
b   c   d

and let $F =\{ bc, bd \}$. When we add $F$ we obtain the cycles $abc$, $abd$ and $acbd$, as I've tried to show in the next diagram.

    a
  / |  \
b - c   d
|_______|