28.1.6. Upper Bounds on Vertex Connectivity and Edge Connectivity

Today, let's start by discussing the concept of vertex cuts. A vertex cut, also known as a separating set, is a subset of vertices in a graph that, when removed, disconnects the graph. Does anyone know what that means?

Does that mean that if I remove those specific vertices, the graph will fall apart?

Exactly! For instance, if we have a graph G and we remove some vertices V', the graph may become disconnected. Remember, we can also think of a cut vertex like an articulation point.

So, can every graph have a cut vertex?

Good question! Every connected graph must have at least one cut vertex, except complete graphs. In complete graphs, removing any vertices still keeps the graph connected!

What about disconnected graphs? Do they have cut vertices?

That's correct, in disconnected graphs, we can't talk about cut vertices in the same way since the graph is already disconnected. In our upcoming lesson, we will introduce the formal definition of vertex connectivity. Let's recap: a vertex cut disconnects the graph when removed, and not all graphs must have a cut vertex, especially not complete graphs.

Now, let's delve into vertex connectivity. It is denoted by κ(G) and defined as the size of the smallest vertex cut. Can anyone explain that in simpler terms?

It's like the minimum number of vertices we have to remove to split the graph, right?

Exactly right! For a graph that has an articulation point, the vertex connectivity could be as low as one. Let's look at a specific graph to illustrate how we determine κ(G).

What if there are no articulation points?

In such cases, we may need to delete multiple vertices. For instance, to disconnect certain graphs, you might remove more than one node that is not a cut vertex. Remember, our definition of vertex connectivity also addresses cases of complete graphs.

That was what you mentioned earlier about complete graphs, right?

Absolutely! In fact, for complete graphs, vertex connectivity can only be calculated as n-1 vertices removed to create a single-node graph. To sum up: vertex connectivity tells us the minimum vertices to remove to disconnect the graph.

Moving on, let’s talk about edge connectivity. An edge cut consists of edges whose removal disconnects the graph. Much like vertex connectivity, we define edge connectivity as λ(G), representing the size of the smallest edge cut.

So if I remove those edges, I would disconnect the graph?

Exactly! To illustrate this, we’d see that if removing certain edges isolates a vertex, we thus consider them as an edge cut. Can someone think of an example in a graph?

If I connect all vertices to a central one and then remove that central edge, isn't that an edge cut?

Exactly! Now similar to vertex connectivity, edge connectivity has upper bounds too. That leads us to the crucial connection between edge and vertex connectivity.

Let’s progress towards understanding the upper bounds on connectivity. For connected, non-complete graphs, we've established that κ(G) is always less than or equal to the minimum degree of the graph. Can anyone articulate why that might be?

If you remove all neighbors of a vertex with the lowest degree, that vertex would disconnect, right?

Exactly! This is crucial. Also, λ(G), the edge connectivity, follows a similar upper bound. So for any connected, non-complete graph, we state, κ(G) ≤ λ(G) ≤ min degree(G).

Is this true even for complete graphs?

Not in the same way, since in complete graphs, both measures equal n-1. Therefore the inequalities solely hold for non-complete graphs. Key takeaway: Understanding connectivity helps in analyzing a graph's resilience.

To wrap up our discussion today, we covered vertex cuts, vertex and edge connectivity, and how to establish upper bounds for these concepts. What are some key points you'd take away?

Vertex connectivity tells us the minimum vertices needed to disconnect a graph.

And edge connectivity does the same but with edges.

Both are bounded by the minimum degree of the graph!

Excellent! You all have grasped the key ideas! Understanding these relationships between connectivity measures is vital for deeper insights in graph theory.