Let G be a graph with n vertices. Prove that there is a subgraph of Kn isomorphic to G. Im unsure how to explain a proof for this. Would I just mention the 4 properties required for a graph to be isomorphic.
Follow Math Help Forum on Facebook and Google+
Make the given graph G as a complete graph $\displaystyle K_n$ by joining all non adjacent vertices. Then obviously $\displaystyle K_n$ contains $\displaystyle G$ as an induced subgraph upto isomorphism.
View Tag Cloud