Skip to main content
fixed some grammar and terminology and added graph minors tag.
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Given a planar graph (no loops, no multiple edge), is it always possible to perform edge contractions* in order to obtain a graph $T$ which has no loops, butand if one forgets the multiplicity of its edgeignores parallel edges, $T$ is a tree?

*delete the edge and identify its two ends. This may create loops and multiple edges in the process.

Is there any characterisation of planar graphs which admitsadmit such contractions?

I somehow thought there was an easy counterexample, but could not find it. Apologies in advance if this is well-known.

Given a planar graph (no loops, no multiple edge), is it always possible to perform edge contractions* in order to obtain a graph $T$ which has no loops, but if one forgets the multiplicity of its edge, $T$ is a tree?

*delete the edge and identify its two ends. This may create loops and multiple edges in the process.

Is there any characterisation of planar which admits such contractions?

I somehow thought there was an easy counterexample, but could not find it. Apologies in advance if this is well-known.

Given a planar graph (no loops, no multiple edge), is it always possible to perform edge contractions* in order to obtain a graph $T$ which has no loops, and if one ignores parallel edges, $T$ is a tree?

*delete the edge and identify its two ends. This may create loops and multiple edges in the process.

Is there any characterisation of planar graphs which admit such contractions?

I somehow thought there was an easy counterexample, but could not find it. Apologies in advance if this is well-known.

added 75 characters in body
Source Link
ARG
  • 4.4k
  • 1
  • 25
  • 46

Given a planar graph (no loops, no multiple edge), is it always possible to perform edge contractions* in order to obtain a graph $T$ which has no loops, but if one forgets the multiplicity of its edge, $T$ is a tree?

*delete the edge and identify its two ends. This may create loops and multiple edges in the process.

Is there any characterisation of planar which admits such contractions?

I somehow thought there was an easy counterexample, but could not find it. Apologies in advance if this is well-known.

Given a planar graph (no loops, no multiple edge), is it always possible to perform edge contractions* in order to obtain a graph $T$ which has no loops, but if one forgets the multiplicity of its edge, $T$ is a tree?

*delete the edge and identify its two ends. This may create loops and multiple edges in the process.

I somehow thought there was an easy counterexample, but could not find it. Apologies in advance if this is well-known.

Given a planar graph (no loops, no multiple edge), is it always possible to perform edge contractions* in order to obtain a graph $T$ which has no loops, but if one forgets the multiplicity of its edge, $T$ is a tree?

*delete the edge and identify its two ends. This may create loops and multiple edges in the process.

Is there any characterisation of planar which admits such contractions?

I somehow thought there was an easy counterexample, but could not find it. Apologies in advance if this is well-known.

Source Link
ARG
  • 4.4k
  • 1
  • 25
  • 46

Contracting a planar graph to a (multiply-edged)-tree

Given a planar graph (no loops, no multiple edge), is it always possible to perform edge contractions* in order to obtain a graph $T$ which has no loops, but if one forgets the multiplicity of its edge, $T$ is a tree?

*delete the edge and identify its two ends. This may create loops and multiple edges in the process.

I somehow thought there was an easy counterexample, but could not find it. Apologies in advance if this is well-known.