0
$\begingroup$

If we had some $K_n$ subgraph where $K_n \subseteq G$, must the complete subgraph $K_n$ be an induced subgraph from $G$? In other words, can we create a situation where we remove vertices from a simple graph $G$ to obtain some complete subgraph where the subgraph was not complete when it was a part of $G$? For example, $n=5$.

$\endgroup$

2 Answers 2

1
$\begingroup$

Let $G$ be a graph, $H$ the graph obtained by removing a vertex, say $u$ from it. Find your desired complete subgraph $K_{n}$ of $H$. Now add $u$ back, with all its edges, to $H$, forming $G$. $K_n$ remains a subgraph of $G$ - any subgraph of a graph $G$ is a subgraph of a supergraph of $G$.

Now, assuming you meant "edges" instead of "vertices" - otherwise I don't see how bringing "induced subgraphs" to the question changes anything. Let $G$ be a graph, $G[S]$ the subgraph induced by $S \subseteq V_{G}$. Suppose we delete some edge $uv$ of $G[S]$ and obtain a new graph, $H$, allegedly complete - a complete subgraph of $G$ that is not induced. But $H$ cannot be complete, since it lacks an edge between vertices $u$ and $v$.

$\endgroup$
0
$\begingroup$

"$K_n \subseteq G$ is an induced subgraph" means "for all vertices $x,y$ in $K_n$, if $(x,y)$ is an edge in $G$ then $(x,y)$ is an edge in $K_n$."

This is obviously true if $K_n$ is complete, because all pairs of vertices in a complete graph are joined by an edge.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .