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 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, $\{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 is a vertex cut, then is called a cut-vertex of .
- At the example, the only cut-vertex is 1.
is said to be $k$ -connected (and sometimes -vertex-connected) if every vertex cut is al least of size .
- 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 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.

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!

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 $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)$ .

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)$ .

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.

Vertex Cut & Cut vertex

Some examples

Bounding the connectivity

The Average degree

Mader’s theorem

The proof

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

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

Part 3 – completing the proof

Base case

Induction step

Case 1

Splitting the graph

Finishing the proof

Summary

Like this:

One thought on “Connectivity”

Leave a Reply Cancel reply

Vertex Cut & Cut vertex

Some examples

Bounding the connectivity

The Average degree

Mader’s theorem

The proof

Part 1 – lower bound for <img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=V%28G%29&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="V(G)" class="latex" />.

Part 2 – lower bound for <img data-lazy-fallback="1" src="https://s0.wp.com/latex.php?latex=e%28G%29&#038;bg=ffffff&#038;fg=394d55&#038;s=0&#038;c=20201002" alt="e(G)" class="latex" />.

Part 3 – completing the proof

Base case

Induction step

Case 1

Splitting the graph

Finishing the proof

Summary

Share

Like this:

One thought on “Connectivity”

Leave a Reply Cancel reply

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

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