# Connectivity

How can we disconnect a graph? Is there a ‘good’ way to do so? How hard we need to work in order to disconnect a graph? Are there graphs that are ‘more’ connected than others?

Well, let’s start answering those questions. the easiest is the first. Of course we can disconnect a graph! There are two ways to do so:

• Remove vertices.
• Remove edges.

However, consider the following graphs:

That’s a really simple graph – It has 5 vertices and 4 edges. In fact, it is even a tree. Let’s see how we can disconnect the graph, starting with vertices:

• If I’ll remove vertex $1$, since all edges are incident to it, we will get a graph with 4 vertices, but with no edges
• On the other hand, any other vertex that I’ll remove, will not disconnect the graph. Moreover, even after removing a vertex which is not one, I can remove another vertex which is not 1 – and the graph will still be connected. In fact, I can remove all the vertices that are not one and still have a connected graph.

So there is something special about the first vertex, we’ll get to that in a moment.

What about edges? It’s not hard to see that every edge that I’ll remove from the graph will disconnect him. In fact – it happens since the graph is a tree (so by definition, it is connected with $n-1$ edges. Removing an edge, will disconnect the graph – since we’ve seen that in a tree there is only one path between two vertices. Therefore, by removing the edge $\{i,j\}$, we obtain that $i$ and $j$ have no path between them).

Ok, Enough with intro, let’s present some new definitions:

## Vertex Cut & Cut vertex

Suppose that $G=(V,E)$ is a graph:

• A set $S\subseteq V$ of vertices is called a vertex cut, if $G\setminus S=G[V\setminus S]$ is not connected, or contains only one vertex. In simpler words – A subset is a vertex cut, if removing the vertices of the set from the graph, yields a disconnected graph.
• At the example in the above, $\{1\}$ is a vertex cut. Moreover, $\{2,3,4,5\}$ is also a vertex cut – since by removing them, we are left with only one vertex.
• If $\{v\}$ is a vertex cut, then $v$ is called a cut-vertex of $G$.
• At the example, the only cut-vertex is 1.
• $G$ is said to be $k$-connected (and sometimes $k$-vertex-connected) if every vertex cut is al least of size $k$.
• In our example – the graph is 1-connected since $\{s\}$ is the smallest vertex cut and it is of size 1.
• In general, any tree is 1-connected! To see that, you can pick a leaf $v$ (and in any tree of size 2 or more, there are at least two leaves). By definition, it has degree one. Suppose that $v$ is adjacent to $u$. Thus, removing $u$ yields a disconnected graph.
• The connectivity of $G$ is denoted by $\kappa(G)$ is the greatest $k$ such that $G$ is $k$-connected.
• From the arguments in the above, we can conclude that the connectivity of a tree is 1.

Alright then, enough with the definitions, let’s see what can we learn from them.

#### Some examples

First, notice that if $G$ is not connected, then $\emptyset$ is already a vertex cut. Therefore, it is 0-connected and has 0 connectivity.

What about $K_n$? Every time you remove a vertex from it, it still stays connected. Here is a quick proof: Suppose that we have removed $v$ from $K_n$. Now, for any two vertices $u,w\in K_n\setminus \{v\}$, the edge $uw$ will still be in the graph after removing $v$.

It’s not hard to see that we can’t disconnect this graph, we can only get a graph with a single vertex (convince yourself) – after removing $n-1$ vertices. Thus, $\kappa(K_n)=n-1$, and $K_n$ has no cut vertices.

That makes great sense – a tree is very ‘fragile’, you can easilly disconnect it. However, the complete graph is “super” connected – no matter what vertices you remove, you will never be able to disconnect it. And finally, the most boring case is a graph that is not connected from the first place. It has connectivity 0, and we need ‘zero effort’ to disconnect it.

### Bounding the connectivity

Can you think of an easy method to disconnect any graph? I have one:

Pick a vertex $v$ in the graph $G$, and remove from the graph all the vertices that are adjacent to $v$. In the new graph, $v$ will be isolated – of course we will then get a disconnected graph / a graph with a single vertex.

How many vertices have we removed in this process? we have removed exactly $d(v)$ vertices!

This process applies to any vertex, therefore, we can pick the vertex with the minimal degree (if you recall, it is denoted by $\delta(G)$). Therefore, we can find a vertex cut with $\delta(G)$ vertices. From that we can conclude that:

\kappa(G)\leq\delta(G)

And that’s a pretty great bound, but in some cases, it is not helpul at all!

In this graph, every vertex has degree 3 – thus $\delta(G) = 3$. However, this is not even a connected graph! Thus, $\kappa(G)=0$. We can present similar examples with two copies (or more) of the complete graph $G=K_n$, where $\delta(G)=n$ and $\kappa(G) = 0$

## The Average degree

I am now going to define the average degree of a graph, just from the name, you probably already know what the definition may be: The sum of vertices divided by the number of the vertices. And that’s exactly what it is. So we define the average degree as:

\overline{d(G)}=\frac{1}{V(G)}\cdot\sum_{v\in V(G)}d(v)

If you recall, in the second post, I’ve proved the degree-sum formula:

\sum_{v\in V(G)}d(v)=2\cdot e(G)

So we can also define the average degree as:

\overline{d(G)}=\frac{2\cdot e(G)}{V(G)}

This is going to be quite handy really soon!

I shall now prove an interesting theorem that shows a relation between the average degree of a graph, and the existence of $k$-connected subgraphs. The theorem helps us to solve our problem from before: Even though the connectivity of a graph might be 0 – not everything is lost! Sometimes, we can still find $k$-connected subgraphs.

The theorem goes like this:

Suppose that $k\geq 0$ and $G$ is a graph with an average degree of at least $4k$. Then $G$ has a $k$-connected subgraph $G^\prime$.

The proof is going to be pretty long, so I’ll split it into parts in order to make it as easy as possible.

#### The proof

The case $k=0$ is trivial – any graph has in it a 0-connected subgraph.

The case $k=1$ is also pretty easy: Since the average degree of $G$ is greater than $4\cdot 1 =4$, then there is an edge in the graph with endpoints $v,u$ (there are many edges actually – but one is enough). Then, the subgraph spanned by $\{v,u\}$ is just the graph $G=(\{v,u\},\{\{v,u\}\})$ and it is indeed 1-connected.

We now assume that $k\geq 2$. I am going to split the rest of the proof into 3 parts:

#### Part 1 – lower bound for $V(G)$$V(G)$.

It turns out that for this theorem I need that $V(G)$ will be greater than $2k -1$.

Since the average degree is $4k$ there has to be a vertex $v$ with degree greater than $4k$ (Why? assume that all the degrees are smaller than $4k$, then so as their average…)

We now have:

V(G)\geq d(v) + 1\geq 4k+1\geq2k-1

[Why $V(G) \geq d(v) + 1$? the degree counts the number of vertices adjacent to $v$ and we add one for the count since we are counting $v$ as well. $d(v) +1$ counts only vertices in $G$ therefore it must be less than the number of all the vertices – $V(G)$.]

#### Part 2 – lower bound for $e(G)$$e(G)$.

Again, as it turns out, proving that:

e(G)\ge (2k-3)(V(G)-k+1)+1

will be enough (the bounds are so weird and they look like a ‘gift from the sky‘, right?).

To see why it’s true, notice that:

\frac{2\cdot e(G)}{V(G)}=\overline{d(G)}\geq 4k

Therefore:

2\cdot e(G)\geq 4k\cdot V(G)\Rightarrow e(G)\geq 2k\cdot V(G)\geq (2k-3)\cdot V(G)

Let’s focus now on the expression:

 (2k-3)(V(G)-k+1)+1

Simplify it a bit to get:

= (2k-3)(V(G)-k+1)+1
=(2k-3)\cdot V(G)+(2k-3)
\cdot(-k+1)+1

You can keep simplifyng it yourself and get:

=(2k-3)\cdot V(G)+(k-2)\cdot(1-2k)

The expression $(k-2)\cdot(1-2k)$ is negative or zero:

• $k-2 \geq 0$ since $k\geq 2$.
• $1-2k < 0$ for every $k\in \mathbb{N}$.

Therefore:

 (2k-3)(V(G)-k+1)+1=(2k-3)\cdot V(G)+\overbrace{(k-2)\cdot(1-2k)}^{\leq 0}\leq(2k-3)^\cdot V(G)

Thus:

e(G)\geq 2k\cdot V(G)\geq (2k-3)\cdot V(G)\geq  (2k-3)(V(G)-k+1)+1

As we wanted.

#### Part 3 – completing the proof

So we know that

• $V(G)\geq 2k-1$
• $e(G)\ge (2k-3)(V(G)-k+1)+1$

Now I am going to show that those conditions are enough for us to find a $k$-connected subgraph.

This is going to be done by induction on $n=V(G)$.

##### Base case

Suppose that $V(G)= 2k -1$. In that case:

e(G)\ge (2k-3)(V(G)-k+1)+1=(2k-3)((2k-1)-k+1)+1
=(2k-3)k+1=2k^2-3k+1=(2k-1)(k-1)=\frac{(2k-1)(2k-2)}{2}

However, $\frac{(2k-1)(2k-2)}{2}$ is exactly the number of edges of the complete graph $K_{2k-1}$

[ To see this, notice that between any two vertices there is an edge. Thus we can treat an arbitrary edge as 2 different endpoints. We have $2k-1$ options to pick the first endpoint, and after we picked it, we have $2k-2$ options to pick the second one – However, in that way we count each edge twice, therefore, we must devide the result by 2]

We got that the number of edges in $G$ is greater or equals the number of edges in $K_{2k-1}$. But $K_{2k-1}$ is the graph with the all the edges possible, therefore $G$ is the complete graph itself!

Now:

\kappa(G)=\kappa(K_{2k-1})=2k-2\overset{k\geq 2}{\geq} k

#### Induction step

We now assume that $n = V(G) > 2k - 1$. There are two cases now:

###### Case 1

There exists a vertex $v\in V$ such that:

d(v)\leq 2k-3

We can now define $H=G\setminus \{v\}$. Then $V(H) = n-1\geq 2k-1$. Thus:

e(H)=e(G)-d_G(v)\geq\overbrace{(2k-3)(V(G)-k+1)+1}^{\leq e(G)}-\overbrace{(2k-3)}^{\geq d_G(v)}
=(2k-3)(n-k+1-1)+1=(2k-3)((n-1)-k+1)+1

We found out that $H$ satisfies the properites, so from the induction we conclude that $H$ as a $k$-connected subgraph – which in particular a subgraph of $G$.

Case 2

For every $v\in V$, $d(v)\geq 2k -2$.

If $G$ is $k$-connected, we are done.

If not, then there is a vertex cut $S$ such that $|S| \leq k-1$. (If there wasn’t, then the graph had to be at least $k$-connected!)

###### Splitting the graph

We are now going to split $V$ into two subsets $V_1,V_2$ such that $V_1\cup V_2 = V$, and $V_1\cap V_2 = S$.

Morevover, I can pick the sets in a way that there will be no edges between $V_1\setminus S$ and $V_2\setminus S$. Let’s see how exactly:

• If the graph is not conncected, we define $S=\emptyset$, pick one component and define the set $V_1$ to be the set of the vertices of the component. Then, $V_2$ will be the rest of the vertices.
• If the graph is connected, then we pick $S$ to be some vertex cut (with size smaller than $k$). Removing the vertices of $S$ from $G$ yields a disconnected graph ($S$ is a vertex cut). Therefore, we can choose one component from $G\setminus S$ and define the set $V_1$ to be the set of the vertices of the component and the vertices from $S$. $V_2$ will be the rest of the vertices and the vertices from $S$.

Great, so after we have picked such sets, we can proceed. Let $v\in V_1\setminus S$ be some arbitrary vertex. We know that:

\deg(v_1)\geq2k-2

(That’s the case we are dealing with…) Therefore, there are at least $(2k -2) +1 =2k-1$ vertices in $V_1$ ( There are $2k-1$ neighbors to $v_1$ and we also count $v_1$ as well).

Similarly, $|V_2|\geq 2k-1$. Denote now:

G_1=G[V_1],G_2=G[V_2]

(The subgraphs that spanned by $V_1,V_2$).

###### Finishing the proof

If:

e(G_1)\geq (2k-3)(|V_1|-k+1) + 1

Then by induction, $G_1$ contains a $k$-connected subgraph. Same goes for $G_2$ as well.

If those are not the cases, then:

e(G_1)<(2k-3)(|V_1|-k+1) + 1\ \ \ \ \ ,\ \ \ \ \ e(G_2)<(2k-3)(|V_2|-k+1) + 1

We is equivalent to:

e(G_1)\leq(2k-3)(|V_1|-k+1)\ \ \ \ \ ,\ \ \ \ \ e(G_2)\leq(2k-3)(|V_2|-k+1)

Notice that:

e(G)\leq e(G_1) +e(G_2)

Since every edge in $G$ appears on $G_1$ or $G_2$. However, we count edges inside $S$ (if there are any) twice! So:

e(G)\leq e(G_1) +e(G_2)\leq\overbrace{(2k-3)(|V_1|-k+1)}^{\leq e(G_1)} + \overbrace{(2k-3)(|V_2|-k+1)}^{\leq e(G_2)}
=(2k-3)(|V_1|+|V_2|-2k+2)=(2k-3)(|V_1|+|V_2|-2(k-1))
\leq(2k-3)(\overbrace{|V_1|+|V_2|}^{V(G)}-(k-1))=(2k-3)(V(G)-k+1)

Therefore:

e(G) <(2k-3)(V(G)-k+1) +1

And that is a contradiction to our assumption!

And that’s it! In all the cases that won’t lead us to a contradiction, we found a $k$-connected subgraph, as we wanted.

## Summary

We’ve seen that some connected graph may be ‘more connected‘ than others. In adittion I proved a pretty cool heorem that has kind of a technical proofs, but it’s really nice to see how picking the ‘perfect numbers’ yields a smooth proof that works perfectly!

All this post was dedicated to vertices, but in the beginning I mentioned that we can also remove edges in order to disconnect a graph. That’s right, we can do it – but we will discuss it in the next post.