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 , 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 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 , we obtain that and have no path between them).

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

## Vertex Cut & Cut vertex

Suppose that is a graph:

- A set of vertices is called a
**vertex cut**, if 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, is a vertex cut. Moreover, is also a vertex cut – since by removing them, we are left with only one vertex.

- If is a vertex cut, then is called a
**cut-vertex**of .- At the example, the only cut-vertex is 1.

- is said to be
**-connected**(and sometimes -vertex-connected) if every vertex cut is al least of size .- In our example – the graph is 1-connected since 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 (and in any tree of size 2 or more, there are at least two leaves). By definition, it has degree one. Suppose that is adjacent to . Thus, removing yields a disconnected graph.

- The
**connectivity**of is denoted by is the greatest such that is -connected.- From the arguments in the above, we can conclude that the connectivity of a tree is
**1**.

- From the arguments in the above, we can conclude that the connectivity of a tree is

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

#### Some examples

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

What about ? Every time you remove a vertex from it, it still stays connected. Here is a quick proof: Suppose that we have removed from . Now, for any two vertices , the edge will still be in the graph after removing .

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 vertices. Thus, , and 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 in the graph , and remove from the graph all the vertices that are adjacent to . In the new graph, 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 vertices!

This process applies to any vertex, therefore, we can pick the vertex with the **minimal **degree (if you recall, it is denoted by ). Therefore, we can find a vertex cut with 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 . However, this is not even a connected graph! Thus, . We can present similar examples with two copies (or more) of the complete graph , where and …

## 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!

## Mader’s theorem

I shall now prove an interesting theorem that shows a relation between the average degree of a graph, and the **existence** of -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 -connected subgraphs.

The theorem goes like this:

Suppose that and is a graph with an average degree of **at least **. Then has a -connected subgraph .

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 is trivial – any graph has in it a 0-connected subgraph.

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

We now assume that . I am going to split the rest of the proof into 3 parts:

#### Part 1 – lower bound for .

It turns out that for this theorem I need that will be greater than .

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

We now have:

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

**[**Why ? the degree counts the number of vertices adjacent to and we add one for the count since we are counting as well. counts only vertices in therefore it must be less than the number of all the vertices – .**]**

#### Part 2 – lower bound for .

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 is **negative** or **zero**:

- since .
- for every .

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

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

This is going to be done by **induction **on .

##### Base case

Suppose that . 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, is **exactly** the number of edges of the complete graph

**[** 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 options to pick the first endpoint, and after we picked it, we have 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 is greater or equals the number of edges in . But is the graph with the all the edges possible, therefore 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 . There are two cases now:

**Case 1**

There exists a vertex such that:

d(v)\leq 2k-3

We can now define . Then . 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 satisfies the properites, so from the induction we conclude that as a -connected subgraph – which in particular a subgraph of .

**Case 2**

For every , .

If is -connected, we are done.

If not, then there is a vertex cut such that . (If there wasn’t, then the graph had to be at least -connected!)

**Splitting the graph**

We are now going to split into two subsets such that , and .

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

- If the graph is not conncected, we define , pick
**one**component and define the set to be the set of the vertices of the component. Then, will be the rest of the vertices. - If the graph is connected, then we pick to be some vertex cut (with size smaller than ). Removing the vertices of from yields a disconnected graph ( is a vertex cut). Therefore, we can choose one component from and define the set to be the set of the vertices of the component
**and**the vertices from . will be the rest of the vertices**and**the vertices from .

Great, so after we have picked such sets, we can proceed. Let 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** vertices in ( There are neighbors to and we also count as well).

Similarly, . Denote now:

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

(The subgraphs that spanned by ).

**Finishing the proof**

If:

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

Then by induction, contains a -connected subgraph. Same goes for 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 appears on or . However, we count edges inside (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 -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.

## One thought on “Connectivity”