Skip to main content
added 90 characters in body
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Given a bi-connected graph $G$, say an edge $e$ is destructive if $G-e$ has a cut-vertex. Say that $e$ is $(T,F_1,F_2)$-critical if there is a spanning tree $T$ and forests $F_1,F_2$ as in you description with respect to which $e$ critical.

  1. Must a $(T,F_1,F_2)$-critical edge be destructive? The answer is no. Here is a example based on the answer given by @smapers.

Here is a $14$ point graph with $38$ edges. If desired, add another $4$ edges on the left and $3$ on the right to make each a $K_7$. Either way, there are no destructive edges. The tree $T$ is the green path, The forest $F_1$ is the red tree And $F_2$ consists of two blue paths. Then the central red edge is critical but not destructive.

enter image description here

If one wants $G$ to have some destructive edges and be exactly bi-connected then, as suggested, add some new vertices and edges making a $K_5$, connect it to the $K_7$ on the left two new edges which will become part of $T$ (which will lose an edge elsewhere to avoid a cycle) and then add enough edges to make $F_1$ and $F_2$ valid.

This illustrates:

  1. Do the $(T,F_1,F_2)$-critical edges include all the destructive edges? Again, no. One can certainly arrange to have some of the destructive edges in $T.$

  2. If $e$ is destructive is there some way to choose the tree and forests so that it is critical? Yes. Assign $e$ to $F_1$ with the rest to be determined. Now $G-e$ is connected with a cut-vertex $v$. Start with all the edges on $v$ and extend that to a spanning tree $T$. Now $G-e-T$ is disconnected with the edgesvertices of $E$$e$ in distinct connected components. So $F_2$ will have those two vertices in distinct distinct trees. HoweverHow ever we form $F_1$ (using $e$ ) and $F_2$, The destructive edge $e$ is critical.

Note that some of the trees in $F_2$ might be isolated vertices.

Given a bi-connected graph $G$, say an edge $e$ is destructive if $G-e$ has a cut-vertex. Say that $e$ is $(T,F_1,F_2)$-critical if there is a spanning tree $T$ and forests $F_1,F_2$ as in you description with respect to which $e$ critical.

  1. Must a $(T,F_1,F_2)$-critical edge be destructive? The answer is no. Here is a example based on the answer given by @smapers.

Here is a $14$ point graph with $38$ edges. If desired, add another $4$ edges on the left and $3$ on the right to make each a $K_7$. Either way, there are no destructive edges. The tree $T$ is the green path, The forest $F_1$ is the red tree And $F_2$ consists of two blue paths. Then the central red edge is critical but not destructive.

enter image description here

If one wants $G$ to have some destructive edges and be exactly bi-connected then, as suggested, add some new vertices and edges making a $K_5$, connect it to the $K_7$ on the left two new edges which will become part of $T$ (which will lose an edge elsewhere to avoid a cycle) and then add enough edges to make $F_1$ and $F_2$ valid.

This illustrates:

  1. Do the $(T,F_1,F_2)$-critical edges include all the destructive edges? Again, no. One can certainly arrange to have some of the destructive edges in $T.$

  2. If $e$ is destructive is there some way to choose the tree and forests so that it is critical? Yes. Assign $e$ to $F_1$ with the rest to be determined. Now $G-e$ is connected with a cut-vertex $v$. Start with all the edges on $v$ and extend that to a spanning tree $T$. Now $G-e-T$ is disconnected with the edges of $E$ in distinct connected components. So $F_2$ will have those two in distinct trees. However we form $F_1$ (using $e$ ) and $F_2$, The destructive edge $e$ is critical.

Given a bi-connected graph $G$, say an edge $e$ is destructive if $G-e$ has a cut-vertex. Say that $e$ is $(T,F_1,F_2)$-critical if there is a spanning tree $T$ and forests $F_1,F_2$ as in you description with respect to which $e$ critical.

  1. Must a $(T,F_1,F_2)$-critical edge be destructive? The answer is no. Here is a example based on the answer given by @smapers.

Here is a $14$ point graph with $38$ edges. If desired, add another $4$ edges on the left and $3$ on the right to make each a $K_7$. Either way, there are no destructive edges. The tree $T$ is the green path, The forest $F_1$ is the red tree And $F_2$ consists of two blue paths. Then the central red edge is critical but not destructive.

enter image description here

If one wants $G$ to have some destructive edges and be exactly bi-connected then, as suggested, add some new vertices and edges making a $K_5$, connect it to the $K_7$ on the left two new edges which will become part of $T$ (which will lose an edge elsewhere to avoid a cycle) and then add enough edges to make $F_1$ and $F_2$ valid.

This illustrates:

  1. Do the $(T,F_1,F_2)$-critical edges include all the destructive edges? Again, no. One can certainly arrange to have some of the destructive edges in $T.$

  2. If $e$ is destructive is there some way to choose the tree and forests so that it is critical? Yes. Assign $e$ to $F_1$ with the rest to be determined. Now $G-e$ is connected with a cut-vertex $v$. Start with all the edges on $v$ and extend that to a spanning tree $T$. Now $G-e-T$ is disconnected with the vertices of $e$ in distinct connected components. So $F_2$ will have those two vertices in distinct distinct trees. How ever we form $F_1$ (using $e$ ) and $F_2$, The destructive edge $e$ is critical.

Note that some of the trees in $F_2$ might be isolated vertices.

Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Given a bi-connected graph $G$, say an edge $e$ is destructive if $G-e$ has a cut-vertex. Say that $e$ is $(T,F_1,F_2)$-critical if there is a spanning tree $T$ and forests $F_1,F_2$ as in you description with respect to which $e$ critical.

  1. Must a $(T,F_1,F_2)$-critical edge be destructive? The answer is no. Here is a example based on the answer given by @smapers.

Here is a $14$ point graph with $38$ edges. If desired, add another $4$ edges on the left and $3$ on the right to make each a $K_7$. Either way, there are no destructive edges. The tree $T$ is the green path, The forest $F_1$ is the red tree And $F_2$ consists of two blue paths. Then the central red edge is critical but not destructive.

enter image description here

If one wants $G$ to have some destructive edges and be exactly bi-connected then, as suggested, add some new vertices and edges making a $K_5$, connect it to the $K_7$ on the left two new edges which will become part of $T$ (which will lose an edge elsewhere to avoid a cycle) and then add enough edges to make $F_1$ and $F_2$ valid.

This illustrates:

  1. Do the $(T,F_1,F_2)$-critical edges include all the destructive edges? Again, no. One can certainly arrange to have some of the destructive edges in $T.$

  2. If $e$ is destructive is there some way to choose the tree and forests so that it is critical? Yes. Assign $e$ to $F_1$ with the rest to be determined. Now $G-e$ is connected with a cut-vertex $v$. Start with all the edges on $v$ and extend that to a spanning tree $T$. Now $G-e-T$ is disconnected with the edges of $E$ in distinct connected components. So $F_2$ will have those two in distinct trees. However we form $F_1$ (using $e$ ) and $F_2$, The destructive edge $e$ is critical.