ABSTRAK Penelitian ini dilakukan untuk mendapatkan sebuah formula penentuan sembarang subgraf Kn dengan n vertex dan (???? − 1) edge merupakan spanning tree atau bukan. Hal ini dilakukan dengan cara mengidentifikasi matriks, yaitu pembentukan adjacency matrix dari semua subgraf Kn dengan n vertex dan (???? − 1) edge secara kombinasi dan dilanjutkan dengan menghitung determinan dari matriks B. Matriks B adalah matriks yang diperoleh dari penghapusan sebuah baris pada incidence matrix dari subgraf Kn dengan n vertex dan (???? − 1) edge. Sembarang subgraf tersebut merupakan spanning tree jika |????????????(????)| = 1. Selain itu, terdapat program yang dibuat dengan aplikasi Adobe Flash CS4 dan CodeBlocks untuk mempermudah mendapatkan semua subgrafnya yang spanning tree atau bukan untuk 2 ≤ ???? ≤ 7. Kata Kunci: subgraf, vertex, edge, spanning tree, adjacency matrix, incidence matrix, determinan. ABSTRACT This research was conducted to obtain a formula determining any subgraph Kn with n vertex and (???? − 1) edge is a spanning tree or not. This is done by identifying the matrix, which is forming the adjacency matrix of all subgraphs Kn with n vertex and (???? − 1) edge in combination and continued by calculating the determinant of matrix B. The B matrix is a matrix obtained from eliminating a line on incidence matrix from subgraph Kn with n vertex and (???? − 1) edge. Any subgraph is spanning tree if |???????????? (????)| = 1. In addition, there is the program created with Adobe Flash CS4 and CodeBlocks applications to make it easier to get all the subgraphs that are spanning trees or not for 2 ≤ ???? ≤ 7. Keywords: subgraph, vertex, edge, spanning tree, adjacency matrix, incidence matrix, determinant.