1
$\begingroup$

If $n$ is a positive integer, how would I show that a subgraph induced by a nonempty subset of the vertex set of $K_n$ is a complete graph?

From what I understand, a complete graph is a graph in which each pair of graph vertices is connected by an edge. So in theory, all values in the subgraph should connect to all values in the subset, right? But how would I show this mathematically?

$\endgroup$
  • 1
    $\begingroup$ Take any pair of vertices $u, v$ of your induced subgraph $G'$. If $u, v$ share an edge in $K_n$, then by the definition of induced subgraph $u, v$ must share an edge in $G'$. As it turns out, $u, v$ share an edge in $K_n$, and so they also do in $G'$. As this is true for any pair of vertices of $G'$, every possible edge is present and it is hence a complete graph. $\endgroup$ – Manuel Lafond Feb 27 '15 at 15:50
  • $\begingroup$ so i can say that u, v is an element of G. u,v is also an element of K_n, so therefore K_n is a complete graph? $\endgroup$ – ShadowViper Feb 27 '15 at 16:22
  • $\begingroup$ Never lose sight of what you know, versus what you are trying to prove ! We already know that $K_n$ is a complete graph. That's by definition. So if your proof ends with "therefore $K_n$ is a complete graph", a fact we already knew, you have a problem. But it's surprising how many 1st year students make that mistake. Anyway, you need to show the other way around. Take $u, v$ two vertices of $G$. The edge $uv$ is in $K_n$, and also an edge of $G$, so therefore $G$ is a complete graph. $\endgroup$ – Manuel Lafond Feb 27 '15 at 18:55

Your Answer

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

Browse other questions tagged or ask your own question.