Miltzow, TillmannTillmannMiltzowSchmidt, Jens M.Jens M.SchmidtXia, MingjiMingjiXia2020-10-212020-10-212014-11-18Discrete Mathematics (2014)http://hdl.handle.net/11420/7629A fundamental theorem in graph theory states that any 3-connected graph contains a subdivision of K₄. As a generalization, we ask for the minimum number of K₄-subdivisions that are contained in every 3-connected graph on n vertices. We prove that there are Ω(n³) such K₄-subdivisions and show that the order of this bound is tight for infinitely many graphs. We further investigate a better bound in dependence on m and prove that the computational complexity of the problem of counting the exact number of K₄-subdivisions is #P-hard.en0012-365X201412238723923-connected graphsCounting K -subdivisions 4CyclesComputer Science - Discrete MathematicsComputer Science - Discrete MathematicsMathematics - CombinatoricsJournal Article10.1016/j.disc.2015.06.0041411.4819v2Other