Let $A\subset \mathbb{R}^n$ be a bounded open subset. The cut locus $C$ of $A$ is defined as the domain of nondifferentiability of $dist_{\partial A}: A\to \mathbb{R}$. 

Blum's Medial Axis Transform (MAT) is the set $$M(A):=\{x\in A ~|~  card|argmin_{y\in \partial A} dist(x,y)|\geq 2\}.$$ 

We find $M(A) \subset C$, although $M(A)$ is not always closed. And also $\overline{M(A)}=C$. 


(1) To answer the question posed in the OP's title: Both the cut locus $C$ and $M(A)$ have the homotopy type of the domain $A$, so if $A$ (or $\Omega$ in the notation of the OP) is contractible, then $C$ and $M(A)$ is contractible. 

This is key property of Blum's Medial Axis Transform and specific to the definition of $C$ as the cut locus of the boundary $\partial A$ for $A$ an open subset of Euclidean space (although some generalizations are available). Constructing a strong deformation retract of the domain onto $C$ is reasonably easy: map every point $x$ to the centre $m(x)$ of the maximal round disk containing $x$ and contained in $A$. (Of course, you need prove this maximal disk is unique and varies continuously with $x\in A$).


(2) The OP wants an explanation for why $C$ is a "locally finite graph". 

Formally speaking, the cut locus $C$ and $M(A)$ is *not* a graph, but a singular subset of euclidean space, and does not have the form $(V,E)$ for a set of "edges" and set of "vertices", etc.. So the question of why the cut locus *is* a finite degree graph is somewhat ill posed. But as the OP's references indicate, the cut locus can be given(!) the structure of a graph *a posteriori*. So the proper question is why this *a posteriori* graph structure is always finite degree at the vertices. But what are the "vertices" and what are the "edges" in a one-dimensional topological space? What is the categorical topological definition of a graph?  (For example, is an edge a graph where every vertex has degree 2?)

I proposed in my thesis that a useful view of singularity type spaces like cut loci, medial axes, domains of discontinuity, spines, souls, etc., is expressed by nontrivial contravariant functors $Z: 2^Y \to 2^X$, where X, Y are source, target mm-spaces respectively. The contravariant functors Z arise from solutions of optimal transport programs. In this case, the functor $Z:2^{\partial A} \to 2^A$ has the explicit form $$Z(B):=\{   x \in A ~|~ M_x \cap \partial A \subset B\}$$ where $B$ is open subset of $\partial A$, and $M_x$ is the maximal disk centred at x with interior contained in $A$. The definition is maybe strange, but i propose its a topological definition, and generalizes to all dimensions. For example, what is the support of $Z$ ? 


(3) Nonetheless, our response is: $C$ is a locally finite graph because of the strict(!) upper semicontinuity of the functor $A\mapsto M(A)$ and $A\mapsto C_A$. More specifically, *if* there was a point $x\in C$ or $x\in M(A)$ which had infinite *degree* (i.e. there were infinitely many branches/edges intersecting at $x$), then the maximal disk centred at $x$ would intersect the boundary $\partial A$ at infinitely many points. 

But for what sets $A$ do maximal disks have infinite intersection? Those sets $A$ whose boundaries $\partial A$ have regions of constant curvature, i.e. circular arcs as arising from disks, or unions of disks, or polygons with special rounded corners. However this leads to contradiction, because the cut locus of disks and arcs, etc., consists of points. And the "degree" of the "graph" at that point becomes zero. This is example of the upper semicontinuity of $M(A)$ and $C$: you can construct sets $A_k$ where the degree of the vertex is becoming arbitrarily large, however in the limit the degree collapses to zero. For example, consider $A_k$ the $k$-sided polygon which limits to the round disk $A_\infty$.

So the OP's question might be equivalently rephrased as: Why does the cut locus fail to be lower semicontinuous?

(3) The MAT (or cut locus) is typically trivalent (all vertices degree 3).  But arbitrarily small deformations can significantly increase the number of edges in $C$, c.f. instability and discontinuity properties of MAT (http://midag.cs.unc.edu/pubs/papers/IJCV03-Katz-BlumMedAxis.pdf). However the homotopy-type of $M(A)$ remains unperturbed (as small perturbations of a boundary $\partial A$ do not affect the connectivity of the perturbed bounded region.)

If the boundary is such that every intersection with a disk is finite, then $C$ will be locally finite. Again, only round boundaries which contain circular arcs will have the property that disks intersect the boundary in infinitely many points, but these do *not* lead to infinite degree in the graph because of the failure of lower semicontinuity precisely in these cases!