# Determine whether a graph is connected after deleting all possible sets of specific size.

Anonymous

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?

edit retag close merge delete

Is it linked to the vertex connectivity? If so you should look at the function vertex_connectivity and edge_connectivity in the documentation.

Otherwise some ideas for a greedy algorithm:

• Use Subsets to iterate over all the subsets of vertices of a given size.
• For each iteration, make a copy of your graph with H = G.copy().
• Use H.neighbors to get the neighbors of a given vertex, and then H.delete_vertex to delete them.
• Then use H.is_connected.
( 2020-09-07 13:46:02 +0200 )edit

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.

( 2020-09-07 20:46:40 +0200 )edit

Sort by » oldest newest most voted

Are you familiar with Python? I think it's an important prerequisite before learning how to use Sage.

My previous comment almost gave the full answer. If there are some functions you don't know how to use, you can always use ? to access the documentation from a notebook, as well as some examples (e.g. type Subsets? in a cell). Here is a possible solution for some graph G

G = graphs.TutteGraph()
G.relabel()

for U in Subsets(G.vertices(), 2): # iterate over the subsets of vertices of size 2
H = G.copy() # copy the graph
H.delete_vertices(flatten([G.neighbors(u, True) for u in U])) # build the list of neighbors of all vertices in the subset and delete them from H
if not H.is_connected(): # test for connectivity
print(U)

more