{title2=$A=I+L_G$}

Take a <star graph> $G$ with center $c$ and four leaves $1,2,3,4$. Let $L_G$ be its <Laplacian matrix> and $I$ the <identity matrix>. In the order $(c,1,2,3,4)$, the original example is
$$
A=I+L_G=\begin{pmatrix}
5&-1&-1&-1&-1\\
-1&2&0&0&0\\
-1&0&2&0&0\\
-1&0&0&2&0\\
-1&0&0&0&2
\end{pmatrix}.
$$
For a nonzero <vector> $u$, its <quadratic form> is
$$
u^TAu=u_c^2+\sum_{i=1}^4u_i^2+\sum_{i=1}^4(u_c-u_i)^2>0.
$$
Thus $A$ is a <symmetric positive-definite matrix> and either ordering below admits a <Cholesky decomposition>. Changing the ordering changes the work, rather than the mathematical solvability.

\b[Center first.] Eliminating $c$ with <pivot element> $5$ leaves the <Schur complement>
$$
S=2I_4-\frac15\mathbf1\mathbf1^T
=\frac15\begin{pmatrix}9&-1&-1&-1\\-1&9&-1&-1\\-1&-1&9&-1\\-1&-1&-1&9\end{pmatrix},
\qquad \mathbf1=(1,1,1,1)^T.
$$
Every pair of leaves now has coupling $-1/5$: six new <edges>, hence six undirected <fill-in> positions. The four remaining <vertices> form a <clique>. In the <Cholesky decomposition>, the first column has $C_{cc}=\sqrt5$ and $C_{ic}=-1/\sqrt5$. The rest of the <lower triangular matrix> is dense. To check that later cancellation does not remove its entries, after $r$ leaves have also been eliminated, the active leaf block is
$$
2I_{4-r}-\alpha_r\mathbf1\mathbf1^T,\qquad
\alpha_r=\frac{2}{10-r},\qquad 0\leq r\leq3.
$$
Indeed a leaf step sends $\alpha$ to $\alpha+\alpha^2/(2-\alpha)$. All active off-diagonal entries remain negative. The successive <pivot elements> in ordinary symmetric <Gaussian elimination>, equivalently the squared diagonals in the <Cholesky decomposition>, are
$$
5,\quad\frac95,\quad\frac{16}9,\quad\frac74,\quad\frac{12}7.
$$
The <Cholesky decomposition> therefore stores $5+4+3+2+1=15$ nonzero entries, including its diagonal.

\b[Leaves first.] Permute to $(1,2,3,4,c)$. Each leaf has only one remaining neighbor, so its elimination changes only the center's diagonal, reducing it by $(-1)^2/2=1/2$. The successive <pivot elements> are $2,2,2,2,3$, and the exact <Cholesky decomposition> is
$$
PAP^T=CC^T,\qquad
C=\begin{pmatrix}
\sqrt2&0&0&0&0\\
0&\sqrt2&0&0&0\\
0&0&\sqrt2&0&0\\
0&0&0&\sqrt2&0\\
-1/\sqrt2&-1/\sqrt2&-1/\sqrt2&-1/\sqrt2&\sqrt3
\end{pmatrix}.
$$
There is no <fill-in>, and only $5+4=9$ nonzero entries in $C$. This is a concrete instance of <leaf elimination of a tree-pattern positive-definite matrix>; its general proof explains why the same idea works on every <tree> pattern. The <minimum degree algorithm> also chooses a leaf at every nontrivial stage of this particular example, but that success gives no general optimality guarantee.

\Image[/sparse-star-elimination-graphs.png]
{title=Eliminating the center of a four-leaf <star graph> creates a <clique>; eliminating leaves creates no <fill-in>}

\Image[/sparse-star-cholesky-patterns.png]
{title=The same <symmetric positive-definite matrix> has 15 or nine nonzero <Cholesky decomposition> factor entries, depending on its ordering}

The input has 13 nonzero <matrix elements> when both symmetric halves are counted, or nine in its lower triangle. The six added undirected <edges> correspond to six added positions in one triangular factor, or 12 positions if both symmetric halves of the filled pattern are displayed. Comparing all 13 input entries directly with the 15 entries of $C$ would mix counting conventions.


 Sparse elimination of a four-leaf star (source code)