How would you intuitively but rigorously explain what the VC dimension is?
Shattered set. First we need a concept of a shattered set. I'll work from a shattered set example in Wikipedia adjusting it to your notation.
The statement that $\mathcal{H}$ shatters $C$ means that for every subset $A \subset C$ there is a set $B\in\mathcal{H}$ such that $B$ &quot;separates&quot; $A$ from $C \backslash A$. Writing this formally:
$$\text{shatters}(\mathcal{H},C) = \forall A \subset C\; \exists B\in\mathcal{H}\;.\;A = B\,\cap A $$
As an example consider the set $C$ of four points on $\mathcal{X} = \mathbb{R}^2$:
$$C = \left\{(0,0); (0,1); (1,0); (1,1)\right\}$$
And the classification class $\mathcal{H}$ being all possible 2D discs on $\mathcal{X} =\mathbb{R}^2$. (Notice that people use the world &quot;class&quot; here, because we are dealing with &quot;set-of-sets&quot; stuff and that might get tricky). Note that a disk can be represented as the set of all points inside the circle.
Now, it turns out that this $\mathcal{H}$ doesn't shatter $C$. The counterexample would be the subset $A$ of &quot;diagonal&quot; points:
$$A = \left\{(0,0); (1,1)\right\} \subset C$$
There is no 2D disk $B\in\mathcal{H}$ (in the context of learning theory, an element/set of the hypothesis class is a hypothesis, which can also be viewed as a function) that satisfies $A = B\,\cap A$.  Intuitively, this means that you cannot use a 2D disk to classify your pair of points $A$ from the rest of the set $C$.
The VC dimension of $\mathcal{H}$ is the maximal cardinality $d$ of the set $C$ that it can shatter. For $d=3$, we can provide tree points $C'$ for which we can easily find all discs that cover all eight possible subsets of $C'$:
$$C' = \left\{(0,0); (0,1); (1,0)\right\}$$
Above we've shown that for a particular set $C$ of $d=4$ points $\text{shatters}(\mathcal{H}, C)$ is false. But we need to prove that it is false for all 4-point sets. To prove this, we  consider a convex hull of an arbitrary set of four points $C = \left\{a;b;c;d\right\}$. In general position, the convex hull is either a triangle or a quad:

In the case of a triangle, we choose the outermost three points as a counterexample set $A$. So, with this (labeling) configuration, you cannot find a disk that covers (i.e. classifies) the outermost three points correctly while excluding the point inside the triangle. In the case of a quad, we choose the pair on the longest diagonal. If any three points lay on a single line, then we choose the pair of outermost points.
This sketches a proof that no $d=4$ point set can be shattered by $\mathcal{H}$, but we've shown that there is a $d=3$ set $C'$ that can be. Concluding that $VCdim(\mathcal{H}) = 3$
Another example is considered on the next page (pg. 71) of the book you've referenced. It again considers 2D plane  $\mathcal{X} =\mathbb{R}^2$ and the classification class $\mathcal{H}$ is all possible axis-aligned rectangles. Authors show a configuration $C$ of four points that can be shattered by $\mathcal{H}$ on the left of figure 6.1. And then provide a proof that no $d=5$ points can be shattered by axis-aligned rectangles. Concluding that VC dimension of their  $\mathcal{H}$ is four.
Hope these examples help. (BTW, note that, it seems that Deep Learning has quite bad VC dimension but it still works somehow - which is rather puzzling).