Collection of Maths Problems

Connectivity of particular graphs

Task number: 3958

• Variant

  Trees.

• Solution

  Every edge of the tree is a bridge, every vertex different from a leaf is an articulation.

  Exceptions are \( K_2 \) – as a complete graph it has a vertex connectivity, and also \(K_1\).

• Answer

  The vertex and edge connectivity of each tree on at least two vertices is 1.

• Variant

  Cycles and their complements.

• Hint

  Use Menger’s theorem.

• Answer

  The cycles have the vertex and edge connectivity 2.

  Complements of \(C_3\) and \(C_4\) are disconnected.

  The complement of the cycle \(C_k\) for \(k\ge 5\) is vertex and edge \((k-3)\)-connected.

• Variant

  Complete bipartite graphs \(K_{m,n}\).

• Answer

  The complete bipartite graph \( K_{m, n} \) has vertex and edge connectivity \( \min \{m,n\} \).

• Variant

  Platonic solids.

• Answer

  The vertex and edge connectivity of a Platonic solid is equal to its degree, ie:

  • The tetrahedron, cube, and dodecahedron have connectivity three.
  • Octahedron has connectivity four.
  • Icosahedron has connectivity five.

• Variant

  Hypercube \( Q_d \) of dimension \( d \).

  Vertices of \( Q_d \) are all strings of length \( d \) consiting of zeros and ones. Two vertices are connected by an edge if the strings differ in exactly one position.

• Answer

  The hypercube \( Q_d \) has vertex and edge connectivity \( d \).

• Variant

  The toroidal grid \( T_d (n) \) of dimension \( d \) for \( n \gg d \).

  Vertices of \( T_d (n) \) are arithmetic vectors from \( Z_n^d \). Two vectors are adjacent, if their difference has in exactly one component \( \pm 1 \) and elsewhere zeroes.

  Hence \( T_1 (n) \) is a cycle on \( n \) vertices, \( T_2(n) \) is a grid \( n \times n \) with the left side glued to the right and the top side glued to the bottom.

• Answer

  The toroidal grid \( T_d (n) \) has vertex and edge connectivity \( 2d \).