Here's a function that takes a graph and a vector of vertices and returns the index of each vertex that is connected to all of the input vertices.
all_connected = function(graph, vertices) {
which(sapply(V(x), function(t) {
all(vertices %in% neighbors(graph, t))
}))
}
Now to apply the function:
# Create a graph
set.seed(2)
x = sample_gnm(20, 50)
all_connected(x, 1:2)
## [1] 6 11