Abstract: A connected graph G is said to be k-extendable if it has a set of k independent edges and each set of k independent edges in G can be extended to a perfect matching of G. A graph G is k-factor-critical if G-S has a perfect matching for any k-subset S of V(G). The basic properties of k-extendable and k-factor-critical graphs have been investigated in [11] and [13]. In this paper, we determine thresholds for k-factor-critical graphs and k-extendable bipartite graphs. For non-bipartite k-extendable graphs, we find a probability sequence, which acts the same way like a threshold. 

Key words: k-extendable, k-factor-critical, threshold