Skip to main content
2 of 2
removed capitals from title
YCor
  • 63.9k
  • 5
  • 187
  • 286

Bramble with order 5 for the Wagner graph

For treewidth $3$, there are four forbidden minors: K5, the graph of the octahedron, the pentagonal prism graph, and the Wagner graph.

This implies that the Wagner graph should have tree-width at least $4$ (since it is a minor of itself).

A graph has a bramble of order k if and only if it has treewidth at least $k − 1$. So the Wagner graph should have a bramble of order $5$.

However, I am struggling to construct such a bramble, nor can I find a paper that provides it to my satisfaction. Could someone please draw me a picture, or even provide a textual representation of a bramble with its corresponding hitting set for the Wagner graph? Or else, explain if I've made a mistake in my understanding?