Graphs, Walks and Connectivity — Examples

Every successive pair in every displayed list is one of $01,12,20,23$, so every list is a walk in $G$.

The list $(0,1,2,1)$ traverses $12$ twice, so it is not a trail. The list $(3,2,0,1,2)$ traverses the distinct edges $23,20,01,12$ but repeats vertex $2$, so it is a trail and not a path.

The list $(3,2,1,0)$ has four distinct vertices, so it is a path. The list $(0,1,0)$ is closed but repeats the edge $01$ and has length $2$, so it is not a cycle.

The list $(0,1,2,0)$ is closed, has length $3$, and has distinct vertices before returning to $0$, so it is a cycle.

The vertices $a,b,c$ reach one another along triangle edges, and $p,q,r$ reach one another along $pq,qr$. No edge joins these two sets, so [F1] gives exactly the two stated components.

The edges $ab$ and $pq$ give the two distances $1$. The path $(p,q,r)$ has length $2$, while $p$ and $r$ are not adjacent, so $d(p,r)=2$.

Since $a$ and $p$ lie in different components, $d(a,p)$ is undefined by [F2]. The triangle is a cycle of length $3$, no cycle can have smaller length, and the path component has no cycle; the girth assertions follow.

Each vertex of $K_5$ is adjacent to the other four vertices, so its degree is $4$; [L1] gives $\mathrm{\mid }E(K_5)\mathrm{\mid }=\left(\genfrac{}{}{0px}{}{5}{2}\right)=10$.

Each vertex of $K_{3,3}$ is adjacent to all three vertices in the opposite part and none in its own part, so all six vertices have degree $3$.

By [L2], $2\mathrm{\mid }E(K_{3,3})\mathrm{\mid }=6\cdot 3=18$, hence $\mathrm{\mid }E(K_{3,3})\mathrm{\mid }=9$.

The vertex set has $\left(\genfrac{}{}{0px}{}{5}{2}\right)=10$ elements by [L1]. For a vertex $A$, its neighbours are the two-element subsets of the three-element complement $\mathrm{\Omega }\setminus A$, so it has $\left(\genfrac{}{}{0px}{}{3}{2}\right)=3$ neighbours. Thus $G$ is cubic and $\delta (G)=3$.

If distinct vertices $A,B$ are disjoint, their union has four elements and there is no two-element subset disjoint from both. If they intersect, their union has three elements and its two-element complement is their unique common neighbour.

Deleting any two vertices leaves a connected graph. Up to relabelling $\mathrm{\Omega }$, two deleted two-element subsets are either the disjoint pair $12,34$ or the intersecting pair $12,13$. In the first case the remaining vertices have the spanning path $13,25,14,35,24,15,23,45$; in the second they have the spanning path $24,35,14,25,34,15,23,45$. Every successive pair displayed is disjoint. Relabelling preserves disjointness, so these cases cover every pair.

There is no triangle: adjacent vertices are disjoint and have no common neighbour by step 1.2. There is no $4$-cycle, because its two opposite vertices would have two distinct common neighbours, also impossible by step 1.2.

Every two distinct vertices are at distance at most $2$: disjoint ones are adjacent, and intersecting ones have the common neighbour from step 1.2. Hence $G$ is connected.

The vertices $12,34,15,23,45$ in that order form a $5$-cycle, since consecutive sets, including $45$ and $12$, are disjoint. With step 2.1 and [F2], this proves $g(G)=5$.

No set of at most two edges disconnects $G$. Indeed, if such a deletion produced a component on a smallest vertex set $S$, then $1\le \mathrm{\mid }S\mathrm{\mid }\le 5$. Writing $e(S)$ for the number of edges inside $S$, cubicity gives $3\mathrm{\mid }S\mathrm{\mid }-2e(S)$ edges leaving $S$. For $\mathrm{\mid }S\mathrm{\mid }=1,2,3$ this number is at least $3,4,5$, since a simple triangle-free graph on those sizes has at most $0,1,2$ edges. For $\mathrm{\mid }S\mathrm{\mid }=4$, the absence of triangles and $4$-cycles makes the induced graph acyclic, so it has at most $3$ edges and at least $6$ edges leave. For $\mathrm{\mid }S\mathrm{\mid }=5$, it is either acyclic with at most $4$ edges or is a chordless $5$-cycle with $5$ edges, so at least $5$ edges leave. Every case has at least three boundary edges, a contradiction. Therefore $\lambda (G)\ge 3$.

Deleting one vertex also leaves a connected graph: choose a second vertex, use step 1.3 on the remaining eight, and then add the second vertex back; it retains at least two of its three neighbours. Step 2.2 covers deletion of no vertices. Thus no vertex cut has size at most $2$, and $\kappa (G)\ge 3$.

By [L2] and step 1.1, $\lambda (G)\le \delta (G)=3$. Together with step 3.2 this gives $\lambda (G)=3$.

Whitney's inequality [L2] and step 4.1 give $\kappa (G)\le 3$, while step 3.3 gives the reverse bound. Hence $\kappa (G)=\lambda (G)=3$; both lower bounds were obtained in steps 3.2 and 3.3, which use the cubic regularity of $G$.

Every vertex of $G$ lies on the six-cycle and has degree $2$. Every vertex of $H$ lies on one of its two triangles and has degree $2$. Thus both degree sequences are $(2,2,2,2,2,2)$.

The graph $G$ is connected, since either direction around the cycle gives a path between any two vertices. The graph $H$ is disconnected, since no edge joins its two triangles.

By [F2], connectedness is invariant under isomorphism, so $G\cong ̸H$. They have the same degree sequence by step 1.1, which refutes the stated claim.

The edges form the triangles $xabx$ and $xcdx$. Every vertex reaches $x$ within its triangle, so every two vertices are joined by a path and $G$ is connected.

The vertex $x$ has degree $4$, while $a,b,c,d$ each have degree $2$. Thus every degree is even by [F1].

Since $x$ has degree $4$, [F2] shows that $G$ is not a cycle graph. Steps 1.1 and 1.2 supply the required connected even-degree counterexample.

The graph is connected, and deleting $v$ separates the two lobes. No deletion of zero vertices disconnects a connected graph, so $\kappa (G)=1$.

In each lobe, $a_i$ and $b_i$ have two neighbours inside the lobe and the neighbour $v$, so degree $3$; $c_i,d_i$ have degree $3$ inside the lobe; and $v$ has degree $4$. Hence $\delta (G)=3$.

Deleting $v{a}_1$ and $v{b}_1$ separates the first lobe from the rest, so $\lambda (G)\le 2$.

Every edge lies on a cycle. The edges $v{a}_i$ and $v{b}_i$ lie on the $4$-cycle $v,a_i,c_i,b_i,v$. Each internal edge incident with $a_i$ lies on the triangle $a_i,c_i,d_i,a_i$, and each internal edge incident with $b_i$ lies on $b_i,c_i,d_i,b_i$. Thus deleting one edge leaves an alternate path between its endpoints and cannot disconnect the graph, so $\lambda (G)\ge 2$.

Steps 1.3 and 1.4 give $\lambda (G)=2$. Together with steps 1.1 and 1.2, this proves $\kappa (G)=1<\lambda (G)=2<\delta (G)=3$ and refutes equality in both Whitney inequalities.

Deleting vertex $4$ retains exactly $12,23,13$, the three edges of a triangle on $1,2,3$. Deleting edge $13$ retains exactly $12,23,34,41$, the four-cycle.

Under contraction of $12$ to $x$, the edge $12$ becomes a loop and is deleted; $13$ and $23$ both become $x3$ and merge; $41$ becomes $4x$; and $34$ remains $34$. The resulting simple edge set is $\{x3,34,4x\}$, a triangle.

Since this triangle is obtained from $G$ by an allowed edge contraction, it is a minor of $G$.