I Prove that complete graphs are subgraphs

[Mr Davis 97]

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]

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

 

[StoneTemplePython]

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$