I'm curious whether a simple graph which contains just one vertex is edge k-connected or vertex k-connected.

Edge-k-connectivity: We theoretically can remove any number of edges and it stays connected. The same with vertexes.

Graph satisfies is edge-k-connectivity: IF we remove any k edges -> Graph still satisfies connectivity.

In this case, the left side of implication is never satisfied so it is False. It the left side is False, then the whole implication is True.

EDIT: Graph -> simple graph

  • $\begingroup$ Seems like a case of statements that are vacuously true. $\endgroup$ – MonadBoy Jan 13 '16 at 9:08

According to conventions that I have seen, edge and vertex connectivity for a single vertex graph is undefined.

If you try to say that the graph is vertex 1-connected or edge 1-connected, you run into an issue.

For example, if a graph is vertex 1-connected, than we can remove one vertex and disconnect the graph. However, if we remove one vertex from the graph, we get the empty graph, which is connected by convention.

Similarly, if we say that the graph is edge 1-connected, then this means that we can disconnect the graph by removing one edge. However, there are no edges to remove, so this doesn't make sense.

  • $\begingroup$ We could have self-loops... $\endgroup$ – MonadBoy Jan 13 '16 at 9:07
  • $\begingroup$ I was assuming simple graphs. $\endgroup$ – Elliot G Jan 13 '16 at 9:08
  • $\begingroup$ I'm not sure I agree: By convention the (vertex) connectivity of a complete graph $K_n$ is $n-1$. So, oddly enough, $K_1$ is an example of a connected graph with connectivity $0$. $\endgroup$ – Casteels Jan 13 '16 at 19:07
  • $\begingroup$ @Casteels like I said, this is just the conventions I have seen. I like the idea of zero connectivity also. $\endgroup$ – Elliot G Jan 13 '16 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.