# Prove that complete graphs are subgraphs

I can see intuitively that each complete graph ##K_n## is a subgraph of complete graph ##K_m## when ##m \ge n##. What would a rigorous proof consist of? This is just out of curiosity.

mfb
Mentor
Just pick n nodes out of Km and "show" that all vertices between them are part of the graph? It is quite trivial, of course.

• Mr Davis 97
StoneTemplePython
Gold Member
if you like adjacency matrices, then up to a graph isopmorphism, you can assume your ##K_n## is always in the top left corner of your adjacency matrix for ##K_m##.

In blocked form that top left ##\text{n x n }## submatrix is given by ##\mathbf J_n - \mathbf I_n## indicating that the submatrix (really, subgraph) is a complete graph, because an ##r## dimensional complete graph is specified by an adjacency matrix of ##\mathbf J_r -\mathbf I_r##

(note ##\mathbf J_r = \mathbf 1_r \mathbf 1_r^T## i.e. it indicates the all ones matrix)

- - - -
if you want to have some fun with the graph isomorphism, you can note that permutation matrices are doubly stochastic, and recall that ##\mathbf P^T = \mathbf P^{-1}## since they are orthogonal, so for any arbitrary permutation matrix ##\mathbf P## in ##\mathbb R^{\text{m x m}}## you have

##\mathbf P\big(\mathbf J_m -\mathbf I_m\big) \mathbf P^T = \mathbf P\big(\mathbf J_m\mathbf P^T\big) - \big(\mathbf P\mathbf I_m \mathbf P^T\big) = \mathbf P\big(\mathbf J_m\big) -\big(\mathbf P \mathbf P^T\big) = \mathbf J_m - \mathbf I_m##

Last edited: