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