0
$\begingroup$

Given a graph $G =(V,E)$ and a subset $S⊆V$, the subgraph of $G$ induced by $S$, denoted $\langle S\rangle$ is the subgraph with vertex set $S$ and with edge set $\{(u,v)\mid u,v\in S \mbox{ and } \{u,v\} \in E\}$ . So, $\langle S\rangle$ contains all vertices of $S$ and all edges of $G$ whose end vertices are both in $S$ .

Determine whether $K_4$ is a subgraph of $K_{4,4}$ If yes, then exhibit it. If no, then explain why not.

1 Answers 1

3

$K_4$ is not a subgraph of $K_{4,4}.$ Why? Because $K_{4,4}$ is bipartite and thus has no triangles, why $K_4$ has 4 triangles.

  • 3
    @Max: By knowing two basic facts, one obvious and one almost obvious. (1) $K_n$ contains a triangle for every $n\ge 3$. This is obvious: pick any three vertices, and they and the edges between them form a triangle. (2) No bipartite graph contains a triangle. This is almost obvious: two of the vertices of any triangle would have to be in the same part of the graph, but there are no edges between vertices in the same part of a bipartite graph.2012-11-17