0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$\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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.