Adding a vertex $x$ adjacent to every vertex in a subdivision in$K_{2,3}$ or $K_4$ is a subdivision of $K_5$ or $K_{3,3}$.

103 Views Asked by At

Why does adding a vertex $x$ that is adjacent to every vertex in a subdivision in $K_{2,3}$ or $K_4$ result in a graph that is a subdivision of $K_5$ or $K_{3,3}$?

1

There are 1 best solutions below

0
On

As you've stated it, the claim is false. If you take $K_4$, subdivide each edge, and add a vertex $x$ adjacent to each vertex, then the resulting graph has ten vertices of degree at least three; way too many to be a subdivision of $K_5$ or $K_{3,3}$.

I suppose that you meant to ask:

Why does adding a vertex $x$ that is adjacent every vertex in a subdivision in $K_{2,3}$ or $K_4$ result in a graph with a subgrpah that is a subdivision of $K_5$ or $K_{3,3}$?

This is true. For example if you take some subdivision of $K_4$, add your vertex $x$, delete every edge between $x$ and a "non-original" vertex of the subdivision of $K_4$, the result will clearly be a subdivision of $K_5$. This is similarly true for $K_{2,3}$.