Walks, Paths and Connectivity

In $G_1$, follow $p \to q \to r \to s \to q \to p$. The edges used are $pq, qr, rs, sq, qp$ — but $qp$ is the same edge as $pq$, used a second time. So this closed walk of length $5$ is not a trail (and, since $p$ and $q$ each occur twice, not a path either).

Follow $t \to p \to q \to r \to s \to q$. The five edges used, $tp, pq, qr, rs, sq$, are all different from each other, so this is a trail. But the vertex $q$ appears twice, as the third and the sixth stop, so it is not a path: the walk passes through $q$ on its way to $r$, then returns to $q$ before finally stopping.

A $4$-cycle needs four distinct vertices joined in a closed loop. Try $p, q, s, t$: the edges $pq$, $qs$, $st$, $tp$ are all present in $G_1$ — the chord $qs$ is exactly what makes this possible — and no vertex repeats before closing back to $p$. So $p \to q \to s \to t \to p$ is a $4$-cycle.

The walk $p \to q \to s \to q \to r$ has length $4$ and ends at $r$, but it visits $q$ twice. Delete everything between the two visits to $q$ — the detour $q \to s \to q$ — and what is left is $p \to q \to r$, a path of length $2$ from $p$ to $r$, and in fact the shortest one, since $p$ and $r$ are not adjacent. This is why a shortest walk between two vertices is always a path: a repeated vertex always hides a shortcut.

Let $H$ consist of three pieces glued by nothing at all: the pentagon-with-chord $G_1$ from the last section (connected internally by its $6$ edges), a separate triangle on $u, v, w$ (edges $uv, vw, wu$), and a single vertex $z$ with no edges whatsoever. No edge joins any of the three groups, so $H$ has exactly $\mathbf{3}$ components, of sizes $\mathbf{5}$, $\mathbf{3}$ and $\mathbf{1}$ — and $5+3+1=9$ accounts for every one of its $9$ vertices.

$H$ has $9$ vertices and $9$ edges — the same count a connected graph on $9$ vertices could have — yet it is not connected. Each new edge can join at most two different components into one, reducing the component count by at most $1$; starting from $3$ components, reaching $1$ needs at least $3-1=2$ new edges, and $2$ is enough (for instance $tu$ and $uz$). So $\mathbf{2}$ edges suffice, and no fewer will do.

Is there a walk from $p$ to $u$ in $H$? Every edge of $H$ lies entirely inside one of the three listed vertex sets, $\{p,q,r,s,t\}$, $\{u,v,w\}$, $\{z\}$, so a walk starting at $p$ can never reach a vertex outside $\{p,q,r,s,t\}$ — in particular never $u$. Contrast this with $p$ and $t$, joined directly by the edge $tp$: they are connected, and in fact adjacent.

The graph on $w,x,y,z$ with edges $wx, xy, yz, zw, xz$ is two triangles, $wxz$ and $xyz$, sharing the edge $xz$ — sometimes called a diamond. In the vertex order $w,x,y,z$ its adjacency matrix is

Row $w$ of $A^2$ comes from $(A^2)_{wj} = \sum_\ell A_{w\ell}A_{\ell j}$, summed over $w$'s neighbors $\ell \in \{x,z\}$. For $j=y$: $(A^2)_{wy} = A_{wx}A_{xy} + A_{wz}A_{zy} = 1\cdot1 + 1\cdot1 = 2$ — the walks $w\text{-}x\text{-}y$ and $w\text{-}z\text{-}y$, matching the $2$ common neighbors of $w$ and $y$. The full matrix is

and its diagonal, $2,3,2,3$, is exactly the degree sequence: a closed walk of length $2$ at $v$ is "step out an edge, step straight back," and there are $\deg(v)$ choices of which edge.

In a simple graph, a closed walk of length $3$ can never repeat a vertex (two equal vertices among $v_0,v_1,v_2$ would force a loop or a repeated edge within a single step), so every closed length-$3$ walk is a genuine triangle, traversed from one of its $3$ vertices in one of $2$ directions — $6$ walks per triangle. So the number of triangles is $\operatorname{tr}(A^3)/6$. Computing $A^3=A^2A$ gives diagonal $2,4,2,4$, so $\operatorname{tr}(A^3) = 2+4+2+4=12$, and the diamond has $12/6=\mathbf{2}$ triangles — exactly $wxz$ and $xyz$, as expected.

$(A^3)_{wx} = 5$. Check this by listing every length-$3$ walk from $w$ to $x$: starting $w\text{-}x\text{-}\Box\text{-}x$ gives $w\text{-}x\text{-}w\text{-}x$, $w\text{-}x\text{-}y\text{-}x$, $w\text{-}x\text{-}z\text{-}x$; starting $w\text{-}z\text{-}\Box\text{-}x$ gives $w\text{-}z\text{-}w\text{-}x$ and $w\text{-}z\text{-}y\text{-}x$ ($w\text{-}z\text{-}x\text{-}x$ is not a walk, since $x\text{-}x$ is not an edge). That is $5$ walks in all, matching the matrix entry.

Let $G$ be the graph on $a,\ldots,g$ with edges $ab, bc, ca, cd, de, ef, fd, fg$ — two triangles joined by a bridge, with a pendant hanging off the second. Test each vertex by deleting it and checking what is left connected: deleting $a$, $b$ or $e$ leaves the rest joined through the other triangle edges, so none of these is a cut vertex. Deleting $c$ splits off $\{a,b\}$ from $\{d,e,f,g\}$; deleting $d$ splits $\{a,b,c\}$ from $\{e,f,g\}$; deleting $f$ splits off $g$ alone. So the cut vertices are $\mathbf{c, d, f}$. The same test on edges shows only $cd$ and $fg$ disconnect $G$ when removed — every other edge sits inside one of the two triangles, which stays connected without any one of its edges — so the bridges are $\mathbf{cd}$ and $\mathbf{fg}$.

The bridge $fg$ has two ends, but only one, $f$, is a cut vertex. $g$ has degree $1$, and deleting a degree-$1$ vertex can never disconnect what remains, since nothing else depended on reaching through it. In general, an endpoint of a bridge fails to be a cut vertex exactly when it is a leaf — compare $c$ and $d$, the two ends of the other bridge $cd$, both of degree $3$ and both cut vertices.

In the "bowtie" graph on $h,i,j,k,l$ with two triangles, $h,i,j$ and $h,k,l$, sharing only the vertex $h$, every edge lies inside a triangle, so there is no bridge at all. Yet $h$ is a cut vertex: deleting it separates $\{i,j\}$ from $\{k,l\}$. So a cut vertex need not be the endpoint of any bridge.

For the graph $G$ of the last section, $\kappa(G)=\lambda(G)=1$: removing the single cut vertex $c$ (or $d$, or $f$) disconnects it, removing the single bridge $cd$ (or $fg$) disconnects it too, and no removal of $0$ vertices or edges can disconnect a connected graph — so $1$ is the smallest number that works, for vertices and for edges alike.

Label the $6$-cycle $1\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}1$. Deleting any single vertex leaves a path on the other $5$ vertices, still connected, so $\kappa \ge 2$. Deleting the two opposite vertices $1$ and $4$ leaves only the edges $23$ and $56$, splitting $\{2,3\}$ from $\{5,6\}$ — so $\kappa(C_6) \le 2$, and together $\kappa(C_6)=2$. The same two numbers work for edges: deleting one edge leaves a connected path, but deleting the two opposite edges $12$ and $45$ splits $\{2,3,4\}$ from $\{5,6,1\}$, so $\lambda(C_6)=2$ as well.

The two arcs of the cycle give two paths from $1$ to $4$ sharing no internal vertex: $1\text{-}2\text{-}3\text{-}4$ and $1\text{-}6\text{-}5\text{-}4$. On the other side, removing the two vertices $2$ and $6$ leaves $1$ with no edges at all, since its only neighbors were $2$ and $6$, while $3,4,5$ stay joined by $34,45$ — so $\{2,6\}$ separates $1$ from $4$, and no single vertex can, since that would force $\kappa(C_6) \le 1$. Both the maximum number of disjoint paths and the minimum separating set have size $\mathbf{2}$, exactly as Menger's theorem predicts.

In the complete graph $K_4$, every two vertices are already adjacent, so by convention $\kappa(K_n) = n-1$; for $K_4$ that is $\kappa=3$. Between any two vertices, say $1$ and $2$, there are $3$ pairwise internally-disjoint paths: the edge $12$ itself, and $1\text{-}3\text{-}2$, $1\text{-}4\text{-}2$ through the other two vertices — using all $4$ vertices and giving exactly $\kappa=3$ independent routes.