如何用Python快速查找指定规模的所有连通子图？

[说明：已有一个快速解决方案发布于相关回答中，但仍需进一步提升速度。]

给定一个包含n个顶点的无向稀疏连通图G，需找到一种快速方法，找出G中所有包含m个顶点的连通子图。已知m远小于n，且图中顶点的度数deg(v)远小于n。

示例中n=5，m=3，对应的4个连通子图为：(0,1,2),(1,2,3),(0,2,3),(2,3,4)

以下使用networkx和ego_graph的代码运行速度极慢，对于n=100、deg(v)=10、m=4的图，耗时约100秒；若n=10000，耗时将极其漫长。

import networkx as nx
import itertools
import time

n=100   #nodes in graph
deg=10  #node degree in graph
m=4     #nodes in subgraph

graph=nx.gnm_random_graph(n,n*deg,seed=1)#construct random graph

starttime=time.time()
G = graph.copy()
all_connected_subgraphs = []
radius=m-1
for n in graph.nodes():
    egoG = nx.ego_graph(G,n,radius=radius,center=False)# all closeby nodes
    for sn in itertools.combinations(egoG, radius):# test all combinations of closeby nodes
        SG=[n,*sn]
        G_sub=G.subgraph(SG)
        if nx.is_connected(G_sub):
            all_connected_subgraphs.append(SG)
    G.remove_node(n)

endtime=time.time()
print(endtime-starttime)        

其中G_sub=G.subgraph(SG)和if nx.is_connected(G_sub):是耗时瓶颈，分别占总计算时间的20%和80%。相关问题中未给出高效解决方案。

内容的提问来源于stack exchange，提问作者granular_bastard