A connected graph G with at least $$2k+2$$ 2 k + 2 vertices is called k-extendable if it has a matching of size k and every such matching can extend to a perfect matching in G. A graph G is an (n, k)-graph if for any set S of n vertices, the subgraph $$G-S$$ G - S is k-extendable. For a surface $$\Sigma $$ Σ , Lu and Wang established the pleasurable formula of the minimum number $$k=\mu (n,{\varSigma })$$ k = μ ( n , Σ ) such that no $${\varSigma }$$ Σ -embeddable graph is an (n, k)-graph by fixing the parameter n. In this paper, we make the other parameter k fixed and figure out the minimum number $$n=\rho (k,{\varSigma })$$ n = ρ ( k , Σ ) such that no $${\varSigma }$$ Σ -embeddable graph is an (n, k)-graph. By the way, the well-known Dean’s formula (Theorem 1.1) can be reproduced. Further, we find out an upper bound on the order of (n, k)-graphs embedded in $${\varSigma }$$ Σ for any non-negative integers n, k with $$k\ge 1$$ k ≥ 1 , $$n+2k\ge 6$$ n + 2 k ≥ 6 and $$(n,k)\ne (0,3)$$ ( n , k ) ≠ ( 0 , 3 ) , which yields two results: (i) there are infinitely many (n, k)-graphs embedded in the sphere (resp. the projective plane) if and only if $$n+2k\le 4$$ n + 2 k ≤ 4 ; (ii) for each surface $${\varSigma }$$ Σ homeomorphic to neither the sphere nor the projective plane, there are infinitely many $${\varSigma }$$ Σ -embeddable (n, k)-graphs if and only if $$n+2k\le 5$$ n + 2 k ≤ 5 or $$(n,k)=(0,3)$$ ( n , k ) = ( 0 , 3 ) .