Prove that a graph is complete multipartite iff it has no $k_1 \bigcup k_2$ as a vertex-induced subgraph.

Question

In graph theory, a part of mathematics, a $k$-partite graph is a graph whose vertices are or can be partitioned into $k$ different independent sets.

A vertex-induced subgraph (sometimes simply called an "induced subgraph") is a subset of the vertices of a graph $G$ together with any edges whose endpoints are both in this subset.

So, i want to prove that a graph is complete multipartite, iff it has no $k_1 \bigcup k_2$ as a vertex-induced subgraph.

$k_1$ is a graph that has just one vertex and no edges. $k_2$ is a graph with $2$ vertices and $1$ edge.

So the union of them makes a graph with $3$ vertices and $1$ edge. Call this graph $H$. I want to prove that a graph like $G$ is complete multipartite iff it has no $H$ as its vertex-induced subgraph.

Thanks in advance.

Answer 1

$\Rightarrow$: Let $u$ be the vertex of the $K_1$ and $v,w$ the vertices of the $K_2$. Suppose $G$ has $H=K_1+K_2$ as induced subgraph. $v$ and $w$ cannot be in the same partite set, so assume $v$ is in partite set $A$, and $w$ in partite set $B$. If $u$ is in $A$, then $uw$ is an edge in $G$, contradiction ($H$ also induces the forbidden edge $uw$). Otherwise $u$ is in $B$ and $uv$ is an edge in $G$, contradiction.

We have shown that $G$ cannot have $H$ as induced subgraph.

$\Leftarrow$: If $G$ has no edge, it is complete multipartite and we are done. If $G$ is complete, it is complete multipartite and we are done.

So $G$ must have two independent vertices. Let $S$ be a maximal independent set in $G$ (we have seen that $S$ has at least 2 vertices and that there is at least one vertex that is not in $S$). Let $s\in S, v\notin S$. $v$ must have an edge to $S$, or we could add it to $S$, contradicting maximality of $S$. Let $vt$ be such an edge (so $t\in S$). Now $s$ must be adjacent to either $v$ or $t$ (or we found an induced $K_1+K_2$) and $s$ certainly is not adjacent to $t$.

We have shown that, for every maximal independent set $S$, every vertex of $S$ is adjacent to every vertex that is not in $S$.

Finally let $t\notin S$ and let $T$ be a maximal independent set containing $t$. $T$ cannot contain a vertex of $S$, since $t$ must have an edge to such vertex.

This implies that $G$ is partitioned by its maximal independent sets, so $G$ must be complete multipartite.

Answer 2

Leen's answer is good, and here's another nice way to phrase the argument for ($\Leftarrow$). Let $\approx$ be a relation on $V^2$ where $u\approx v$ if either $u=v$ or $u$ is not adjacent to $v$. I claim that $\approx$ is an equivalence relation. Indeed, reflexivity and symmetry are immediate, so we only need to justify transitivity. Suppose $x\approx y$ and $y\approx z$ but $x\not\approx z$. This means that $xy$ and $yz$ are not edges, but $xz$ is. In other words, $xyz$ forms a copy of $K_1\cup K_2$; a contradiction. Thus, $\approx$ is an equivalence relation, so partition $V$ into the equivalence classes $V_1,\dots,V_k$. Each $V_i$ is an independent set and there must be an edge between any two vertices in different classes.