A graph is called strongly Menger-edge connected (SME-connected) if any two vertices are connected by as many edge-disjoint paths as their smaller degree. For positive integers t and r, a graph G is called t-edge-fault-tolerant SME-connected (t-EFT-SME-connected) of order r if G−F is SME-connected for any set F of edges in G with |F|≤t and δ(G−F)≥r. We show that the n-dimensional folded crossed cube is (n−1)-EFT-SME-connected of order 1 and (3n−5)-EFT-SME-connected of order 2. Let p(G,f) and pM(G,f) be the probabilities that G is connected and SME-connected when f edges are faulted randomly, respectively. We perform a numerical simulation on p(G,f) and pM(G,f) for a five-dimensional folded crossed cube and folded hypercube. The numerical results show that, in addition to their same edge connectivity and SME connectivity, these two graphs have almost the same values of p(G,f) and pM(G,f) for every f. This hints that, although the ‘edge-cross’ pattern in a hypercube-based graph can shorten the mean vertex distance, the ‘edge-cross’ is not a necessary pattern for strengthening the connectivity of the graph.