Prove that G is $K_4$-minor free.

Question

I am asked to solve the following 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.

I understand one of the definition of a graph is $K_4$-minor free if and only if it is series-parallel, so i need to prove the union of two $K_4$-minor free graphs is series-parallel.

It is make sense to say union of 2 series-parallel graph can be also have series composition and parallel composition; since we can just put them together up and down for series composition; and combining the upper and lowest vertices for the parallel composition. Are there any way to proving it mathematically?

Thanks

Answer 1

Hint: If $G$ did have $K_4$ as a minor, then either (a) or (b) below must hold:

(a) There are

• (i) 3 vertices in $H_1$--where at least two of these 3 vertices $v_1,v_3$ are not $v$,

• (ii) a vertex $v_4 \in H_2 \setminus \{v\}$, and

• (iii) a path $P_{14}$ from $v_1$ to $v_4$, and $P_{34}$ from $v_3$ to $v_4$, such that $P_{14}$ and $P_{34}$ intersect precisely at $v_4$.

(b) There are

• (i) 2 vertices $v_1$ and $v_3$ in $H_1 \setminus \{v\}$,

• (ii) 2 vertices $v_2$ and $v_4$ in $H_2 \setminus \{v\}$, and then

• (iii) [among other things] two vertex-disjoint paths $P_{12}$ and $P_{34}$ where $P_{12}$ has one endpoint as $v_1$ and $v_2$ as the other endpoint, and $P_{34}$ has has one endpoint as $v_3$ and $v_4$ as the other endpoint.

[Make sure you see why either (a) and (b) must be so for there to be a $K_4$-minor in $G$.] But (a) is impossible, as $P_{14}$ and $P_{34}$ must also contain $v$ as well [why?]. So (a) cannot be. One can use a similar line of reasoning to show that (b) is impossible as well [make sure you see why for yourself]. Thus there is no $K_4$-minor in $G$.