Simple Graph which is finite and has no K2 as minor.

Question

I have to think about the graphs which are simple and finite.

(a) doesn't have K2 as minor

(b) doesn't have K3 as minor

(c) doesn't have K3 as minor and its a connected graph

(d) doesn't have K1,3 as minor

I just started to study graph theory and have no idea from where to think about.. please help me!

Answer 1

Hints:

If a graph doesn't have $K_2$ as a minor... then in particular it doesn't have $K_2$ as a subgraph. Now... remember that a $K_2$ looks like the following: $\circ - \circ$... it is a graph with two vertices and an edge connecting them.

If a graph doesn't have $K_2$ as a minor then it doesn't have any edges($\dagger$). We call such a graph ______

---

Now, remember what a $K_3$ looks like. If a graph doesn't have $K_3$ as a minor... then not only does it not have $K_3$ as a subgraph, but it doesn't have $K_3$ as a topological minor either. This will imply that...

The graph doesn't have any cycles($\dagger$). We call a graph with no cycles a _______

I intentionally glossed over details. Make sure that you can prove those statements that I marked with a ($\dagger$). It might be easiest to do so via contrapositive, that is, to suppose that you do have the described feature and prove that that implies you would have the described minor.

The remaining two parts to the problem are similar.