Prove that $G$ is $K_4$-minor free

Question

Suppose that $H_1$, $H_2$ are $K_4$-minor free graphs and let $G$ be formed by taking the union of $H_1$ and $H_2$ intersecting in a single vertex $v$. Prove that $G$ is $K_4$-minor free.

How do I do this question? All I know so far is that $H_1$ and $H_2$ are $K_4$-minor free graphs which means that $H_1$ and $H_2$ are series parallel (according to our notes).

Furthermore, if $H_1$ and $H_2$ are series parallel then they can be formed from $K_2$ by subdivisions and double edges.

However, how do I proceed with the question? How do I prove that $G$ is $K_4$-minor free?

Thank you

Answer 1

Suppose that $G$ contains a $K_4$ minor. Since $H_1$ and $H_2$ have no $K_4$ minor themselves, any $K_4$ minor has a vertex $a$ in $H_1$ and a vertex $b$ in $H_2$, both of which are not $v$. Now either $v$ is in the minor or it is not.

If it is, there has to be a path from $a$ to $b$ not using $v$ since the minor is $K_4$. However, as $v$ is a cut-vertex, any path from $a$ to $b$ must pass through $v$ – contradiction.

If it is not, the other two vertices of the minor have to lie strictly within $H_1$ or $H_2$. Without loss of generality, let a third vertex of the minor $c$ be in $H_2$. Then the paths from $a$ to $b$ and from $a$ to $c$ must not share any intermediate vertices, but again, since $v$ is a cut-vertex, those paths must share that vertex – contradiction.

Thus $G$ has no $K_4$ minor.

Answer 2

It might be easiest to prove the contrapositive: suppose $G$ has a $K_4$ minor, and prove that this leads to a contradiction.

Then there is a subgraph $H$ containing distinct vertices $a,b,c,d$ in $G$ connected to each other by vertex-disjoint paths in $G$. Now $H$ is entirely contained in either $H_1$ or $H_2$ (so one of these two graphs must contain a $K_4$ minor), or otherwise (without loss of generality) vertex $a$ and $b$ are both in $H_1$ (excluding $v$), while vertex $b$ is in $H_2$ (exluding $v$).

There are then two paths from $a$ to $c$ and from $b$ to $c$. What do paths in $G$ look like (where do their edges come from)? What happens to $v$? Are these paths vertex-distinct?