# How to mathematically prove edge and vertex connectivity of a graph $G$?

I was wondering if I were given an exercise where I have to find edge and vertex connectivity of a graph which representation is given and if its obvious from the image that edge and vertex connectivity is for example 3, do I have to prove that and what is the way to do so instead of writing every single combination?

Let this be an example :

It is obvious that after removing edges $$b$$,$$c$$ and $$a$$ graph becomes disconnected and thus the edge-connectivity is 3. So now I know that vertex connectivity has to be $$\leq 3$$ from $$\delta(G) \ge \kappa_e (G) \ge \kappa_v (G)$$ where $$\kappa_e(G)$$ is edge-connectivity and $$\kappa_v(G)$$ is vertex-connectivity. We can also see that vertex connectivity is $$2$$ because there is no way to remove one vertex so that graph becomes disconnected. $$2$$ is the minimum number of vertices needed to disconnect graph after their removal.

How do I mathematically prove this?

• usually one argues exactly as you did. Note that you have only proven edge connectivity ≤ 3. You still have to show the other inequality. In this example you almost have 2 complete graphs, this could help. Commented Jun 15, 2021 at 12:38
• @MorganRodgers To be precise, I was curious if my answer is sufficient? Is there a better way to say so? Commented Jun 15, 2021 at 12:49

I think this is a great question.

To give a formal proof, you would have to have a formal description of the graph in the first hand. As long as you only have a picture I would say arguing with the picture is formal enough.

You could say that your graph is obtained from three graphs $$G,G‘,H$$, where $$G,G‘$$ are copies of $$K_5$$ with a unique edge $$xy$$ respectively $$x‘y‘$$ removed, and where $$H$$ is a $$P_3$$ on vertices $$a,b,c,d$$. Your graph is obtained by gluing those graphs together by letting $$a=x, b=x‘, c=y, d=y‘$$.

By construction any path from $$G$$ to $$G‘$$ has to go through one of $$a$$ or $$c$$. Hence deleting $$a,c$$ disconnects the graph and deleting $$ab, bc, cd$$ does as well. This shows $$\kappa_v \leq 2$$ and $$\kappa_e \leq 3$$. To show that those inequalities are in fact equalities we note that deleting a single vertex does not disconnect $$G$$ or $$G‘$$ because they are 3-vertex-connected graphs. So the only thing to check is that picking a vertex in $$G$$ and one in $$G‘$$ we have a path connecting them. But this is true, since out of $$\{a,c\}$$ we at most deleted one vertex.

The case of edge connectivity is similar, but requires us to make a case distinction over from which graphs $$G,G‘,H$$ we delete edges (eg. one from $$G$$, one from $$G‘$$…).

• I really appreciate your answer. This is exactly what I needed. Thanks for the clarification! Commented Jun 15, 2021 at 19:25

There's always a risk when you use the word "obvious" in an undergraduate homework problem that you are hand-waving away the very thing the professor wanted you to demonstrate. You're not wrong with your conjectures, but it is worth a few sentences to demonstrate your understanding of the subject.

To show that the edge connectivity of the graph is 3, you also need to show that there is no 2-edge cut that would disconnect the graph. The most straightforward way to do that is to show that any two vertices of the graph are connected by three disjoint paths. Similarly, you can prove that the vertex connectivity is 2 by showing that there any two points can be connected by two paths that share no vertices aside from the origin and terminus.