The subnetwork reliability of the interconnection network of a multiprocessor system is a key indicator to assess the performance of the multiprocessor system. In order to characterize the fault tolerance of (n-m,k-m)-star graph subnetworks in an (n,k)-star graph, the probability of existing fault-free (n-m,k-m)-star graph subnetworks in an (n,k)-star graph under probabilistic fault condition is analysed. For 1≤k≤n -1 and 1≤m≤k -1, the theoretical formulas of the upper and lower bounds of the probability of existing (n-m,k-m)-star graph subnetworks are obtained, and an algorithm for searching fault-free (n-m,k-m)-star graph subnetworks in an (n,k)-star graph with only node failures is given. Moreover, an approximate method for evaluating the existence probability of fault-free (n-m,k-m)-star graph subnetworks is given based on Monte Carlo simulation. The experimental results show that the upper and lower bounds of the probability of existing (n-m,k-m)-star graph subnetworks are basically consistent with the approximate evaluation results as the node reliability gradually becomes smaller, and the relatively accurate evaluation result can be obtained by the approximate method based on Monte Carlo simulation when the node reliability is relatively high or the difference between the upper and lower bounds of the probability of existing (n-m,k-m)-star graph subnetworks is significant.