Finding a spanning subgraph that satisfies a given condition

edit

Finding a spanning subgraph that satisfies a given condition is NP-hard. My goal is to find a 4-connected planar spanning subgraph of a given graph. I tried writing the following code, but its efficiency is poor, since it enumerates even disconnected spanning subgraphs. I'm wondering whether there are any improvements that could be made to make the algorithm more efficient—at least to make it work on the following specific graph (constructed by drawing a pentagram inside each face of an dodecahedron).

g=Graph({0: [1, 2, 18, 19, 3, 8, 9, 10, 11],
 1: [0, 2, 3, 19, 6, 7, 8, 9, 10],
 2: [0, 1, 3, 19, 4, 5, 6, 7, 8],
 3: [0, 1, 17, 2, 18, 19, 4, 5, 6],
 4: [16, 17, 2, 18, 3, 19, 5, 6, 15],
 5: [16, 17, 2, 3, 4, 6, 7, 14, 15],
 6: [1, 2, 3, 4, 5, 7, 8, 14, 15],
 7: [1, 2, 5, 6, 8, 9, 13, 14, 15],
 8: [0, 1, 2, 6, 7, 9, 10, 13, 14],
 9: [0, 1, 7, 8, 10, 11, 12, 13, 14],

 10: [0, 1, 18, 19, 8, 9, 11, 12, 13],
 11: [0, 16, 17, 18, 19, 9, 10, 12, 13],
 12: [16, 17, 18, 9, 10, 11, 13, 14, 15],
 13: [16, 7, 8, 9, 10, 11, 12, 14, 15],
 14: [16, 5, 6, 7, 8, 9, 12, 13, 15],
 15: [16, 17, 4, 5, 6, 7, 12, 13, 14],

 16: [17, 18, 4, 5, 11, 12, 13, 14, 15],
 17: [16, 18, 3, 19, 4, 5, 11, 12, 15],
 18: [0, 16, 17, 19, 3, 4, 10, 11, 12],
 19: [0, 1, 17, 18, 2, 3, 4, 10, 11]})

def find_one_planar_spanning_subgraph_with_connectivity_at_least(G, k):
    """
    Search for one spanning subgraph of G that is:
        - connected,
        - planar,
        - and has vertex connectivity at least k.

    Parameters:
        G: A SageMath graph.
        k: Minimum required vertex connectivity.

    Returns:
        A graph H (spanning subgraph of G) satisfying all conditions, or None if none exists.
    """
    edges = G.edges(labels=False)
    n = len(edges)

    for i in range(2^n):
        selected_edges = [edges[j] for j in range(n) if (i >> j) & 1]

        H = Graph()
        H.add_vertices(G.vertices())
        H.add_edges(selected_edges)

        # Check all conditions
        if H.is_planar() and H.vertex_connectivity() >= k:
            return H

    return None