Diestel multigraph separation

Question

Hi am reading Diestel graph theory. In the 5th edition, in Chapter 1.10, it says:

The ends of loops and parallel edges in a multigraph G are considered as separating that edge from the rest of G. The vertex v of a loop e, there- fore, is a cutvertex unless ({v}, {e}) is a component of G, and ({v}, {e}) is a ‘block’ in the sense of Chapter 3.1. Thus, a multigraph with a loop is never 2-connected, and any 3-connected multigraph is in fact a graph.

I don't understand what this means, or why we are defining separation like this. Please can someone explain?

I looked at the answer here: Definition of 2-connectedness in multigraphs which answers my first question, except idk what they mean: is it "add a vertex on each edge for ALL sets of parallel edges"? or "add a vertex on all edges parallel to a given edge (which itself doesn't get a vertex)?"

Also I totally don't see the benefit of defining things like this, what are the advantages?

Thanks,

Kevin

Answer 1

There are two parts of this: defining connectivity in the presence of loops, and defining it in the presence of parallel edges.

---

Diestel spends most of this paragraph talking about what happens for loops: we just consider any vertex with a loop to be a cut vertex, except when that vertex is in a connected component by itself, and has exactly one loop. This is a weird exception, but it will be justified.

I think Diestel is on firm ground here. Several things about vertex connectivity go wrong unless you do something about loops. For example, we would like it to be the case that when you subdivide an edge in a $2$-connected graph (replacing it by a path of length $k$ whose internal vertices are completely new to the graph; informally, "drawing some dots" on the edge) the new graph is also $2$-connected. This is not true if you subdivide a loop. Also, we would like it to be the case that a plane graph is $2$-connected if and only if its dual is $2$-connected. This is also false if we're not careful about loops.

Some alternatives are:

• West's Introduction to graph theory just assumes that graphs have no loops in the chapter on connectivity.
• Bondy and Murty's Graph theory defines a cut vertex in the usual way, but defines a separating vertex to be a vertex $v$ such that $G$ is the union of two graphs, each with at least one edge, that only have vertex $v$ (and no edges) in common. Then a vertex with a loop and at least one more edge is a separating vertex, but not a cut vertex.

I think Bondy and Murty's approach is the most helpful for understanding what is going on here: the notion of a separating vertex is one that generalizes to everything Diestel wants to say about loops. In fact, it also explains what Diestel thinks about isolated vertices: they are cut vertices if they have $0$ loops or $1$ loop, but not if they have $2$ or more loops. That is exactly when Bondy and Murty define the isolated vertex to be a separating vertex.

---

Diestel also seems to claim that in any multigraph $G$ where two vertices $u$ and $v$ are connected by two or more parallel edges, the set $\{u,v\}$ is to be considered a vertex cut, even if $G- \{u,v\}$ (which gets rid of any number of parallel edges) is still connected.

Here, I cannot see why Diestel does so, and no other sources seem to be doing anything similar. (For the most part, in other textbooks, the connectivity of a multigraph with parallel edges is treated in the same way as the connectivity of the underlying simple graph.)

There are some results about $3$-connected planar graphs as well: their plane embeddings are combinatorially unique, and their dual graphs are simple. As far as I can tell, these continue to hold for multigraphs with some parallel edges in which the underlying graph is $3$-connected, and there is no need for Diestel's definition.