Prove that complete graphs are subgraphs

  • #1
1,456
44
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.
 

Answers and Replies

  • #2
34,655
10,797
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.
 
  • Like
Likes Mr Davis 97
  • #3
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,167
569
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:

Related Threads on Prove that complete graphs are subgraphs

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
5
Views
10K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
4
Views
2K
Top