Skip to main content
1 of 2

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?