Determine whether a graph is connected after deleting all possible sets of specific size.
I have a graph of 60 vertices. I want to delete the vertices {u, v, N(u), N(v)} and check whether the resulting graph is connected, where u and v are vertices and N(u) and N(v) are their corresponding neighbors.
How can I write a code that covers all the possibilities?
Is it linked to the vertex connectivity? If so you should look at the function
vertex_connectivity
andedge_connectivity
in the documentation.Otherwise some ideas for a greedy algorithm:
Subsets
to iterate over all the subsets of vertices of a given size.H = G.copy()
.H.neighbors
to get the neighbors of a given vertex, and thenH.delete_vertex
to delete them.H.is_connected
.Thank you for your response. My problem is how to write the code? I was thinking of the following Pseudocode: G= graph
V= set of vertices
for i in V, for j in V-{i}
A= G.neighbors(i)
B=G.neighbors(j)
H= G.delete_vertices(A U B)
if H.is_connected()=False
print({i,j})
I don't know how to try this using mathsage.