# 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
2019 Award
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: