Counting K4K4-subdivisions

A fundamental theorem in graph theory states that any 3-connected graph contains a subdivision of K4K4. As a generalization, we ask for the minimum number of K4K4-subdivisions that are contained in every 3-connected graph on nn vertices. We prove that there are Ω(n3)Ω(n3) such K4K4-subdivisions and show that the order of this bound is tight for infinitely many graphs. We further investigate a better bound in dependence on mm and prove that the computational complexity of the problem of counting the exact number of K4K4-subdivisions is #P#P-hard.