# Determine if subgraph and exhibit if so

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.

-

$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.
@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. – Brian M. Scott Nov 17 '12 at 9:02