Let's solve Exercise 4.5 step by step:

Statement: If there is a pair of vertices $a, b \in G$ and an $a, b$-separator $S$ of size $k$, then $\kappa(G) \leq k$.

Solution:

1. Definitions Recap:

   • An $a, b$-separator is a subset of vertices $S \subset V(G)$ such that if we remove $S$ from the graph, there is no path connecting $a$ to $b$ in the resulting graph $G - S$.
   • The connectivity $\kappa(G)$ of a graph is the largest integer $k$ such that the graph remains connected after removing any set of fewer than $k$ vertices.

2. Explanation:

   • If $S$ is an $a, b$-separator with size $k$, this means that removing the $k$ vertices in $S$ disconnects $a$ from $b$. In other words, there is a set of $k$ vertices whose removal disconnects the graph.
   • By definition, the connectivity $\kappa(G)$ of a graph is the maximum $k$ for which the graph remains connected for all possible sets of fewer than $k$ vertices being removed. Since the removal of the $k$-vertex set $S$ disconnects the graph, $\kappa(G)$ cannot be larger than $k$.

Thus, we conclude that if there exists an $a, b$-separator of size $k$, then $\kappa(G) \leq k$.

Statement: $\kappa(G)$ is the minimal size of an $a, b$-separator, taken over all pairs $a, b$ of non-adjacent vertices.

Solution:

1. Explanation:
   • By definition, $\kappa(G)$ represents the largest number $k$ such that removing any set of fewer than $k$ vertices does not disconnect the graph.
   • If we consider all pairs of non-adjacent vertices $a$ and $b$, we are interested in the smallest $k$ such that there exists an $a, b$-separator of size $k$. This smallest $k$ indicates the minimum number of vertices that need to be removed to separate any two non-adjacent vertices in the graph.
   • Therefore, $\kappa(G)$ corresponds to the minimal size of an $a, b$-separator over all possible pairs of non-adjacent vertices in the graph, as this size represents the critical threshold for connectivity.

In conclusion, these statements correctly relate the concept of graph connectivity $\kappa(G)$ to the sizes of separators for pairs of non-adjacent vertices.

Would you like further details on any of the points? Here are some related questions to expand your understanding:

1. What is the relationship between edge-connectivity and vertex-connectivity?
2. How does adding an edge in a graph affect its connectivity $\kappa(G)$?
3. What is Menger’s theorem, and how does it relate to $a, b$-separators?
4. How can the connectivity $\kappa(G)$ be used to classify different types of graphs?
5. How does the structure of the graph change when $\kappa(G)$ is reduced?

Tip: Always try visualizing a graph and experimenting with different configurations of separators to better understand connectivity properties.