For each triangulation $\mathcal{T}$, associate a graph $G_\mathcal{T}$ with vertex set $\mathcal{T}$ (set of triangles) and an edge between two vertices if and only if they share an edge in $\mathcal{T}$. It is well-known that $G_\mathcal{T}$ is a tree. Now, notice that we can remove some diagonals of $\mathcal{T}$ and end up with all regions as quadrilaterals if and only if $G_\mathcal{T}$ has a perfect matching. And that $\mathcal{T}$ is beautiful if and only if number of odd components in $G_\mathcal{T}-v$ is exactly one for all vertices of $G_\mathcal{T}$. The following lemma finishes the problem: Lemma. A tree $T$ has a perfect matching if and only if for every $v\in V(T)$, number of odd components in $T-v$ is exactly one. Proof. Suppose that $T$ has a perfect matching $M$ and $v\in V(T)$. Let $vw\in M$. Then, every component of $T-v$ except for that containing $w$ has even number of vertices, and the component containing $w$ has odd number of vertices. Now, suppose that for every $v\in V(T)$, number of odd components in $T-v$ is exactly one. Choose a leaf $\ell$ of $T$ and let $v$ be its neighbor. Now, consider the graph $T-v$. Then, except for $\lbrace\ell\rbrace$ , every component T_i of $T-v$ has even number of vertices. We claim that for any such component $T_i$, and arbitrary $w\in V(T_i)$, the number of odd components of $T_i-w$ is exactly one. Note that $T-w$ and $T_i-w$ has same connected components except for one component (the component containing $v$ and $\ell$ in $T-w$). However, note that the difference in number of vertices of this component is $|T-T_i|$ which is even. Therefore, connected components of $T-w$ and connected components of $T_i-w$ has same parities and thus $T_i-w$ also has exactly one odd component. By induction, we can find matchings $M_i$ in each $T_i$ and consequently, $\lbrace\ell v\rbrace \cup \left(\bigcup_{i} M_i\right)$ is a perfect matching of $T$ that we are looking for. $\square$.