Proof of Graph Subdivision

57 Views Asked by At

Prove that every simple graph of order $n ≥ 4$ and size at least $2n − 2$ contains a subdivision of $K_4$.

1

There are 1 best solutions below

0
On

This is Exercise 8.3.1 page 132 of Bondy's book "Graph Theory with Applications". There is a hint for this exercise on page 238 of the same book.