Prove $\sqrt{x_1^2+4x_1x_2+5x_2^2+2x_1+6x_2+5}$ is convex

Extended hint: a non-negative quadratic function with positive-definite $A$ can be written as $$ x^TAx+b^Tx+c=\|M(x-x_0)\|^2+d^2. $$ It can be done by completing the square in $x$ or simply identifying $M$, $x_0$ and $d$ from the equation: $A=M^TM$, $d^2$ is the minimum value ($3$ in your case) and $x_0$ is the minimizer.

Now the function you are dealing with is $$ f(x)=\left\|\begin{matrix}M(x-x_0)\cr d\end{matrix}\right\|. $$ It could be proven to be convex directly by definition using triangle inequality (or as a composition of the convex norm-function and the affine one).

Note that $$ x^\top A x + b^\top x + c = \begin{bmatrix}x^\top&1\end{bmatrix}\begin{bmatrix}A&b/2\\b^\top/2 & c\end{bmatrix}\begin{bmatrix}x\\1\end{bmatrix} = \tilde{x}^\top\tilde{A}\tilde{x}. $$

Now, we test $\tilde{A}$ for positive definiteness by calculating its principal minors (I'll skip most of the calculations). We have $$ A = \begin{bmatrix}1&2\\2&5\end{bmatrix},\quad b=\begin{bmatrix}2\\6\end{bmatrix},\quad c = 5, $$ thus, the first principal minor is $1$, and we have $\det(A)>0$, which is the second principal minor of $\tilde{A}$. All that remains is to test $\det{\tilde{A}}$, which is (using Schur): $$ c\det(A - \frac{bb^\top}{4c}) = 5\begin{vmatrix}1 - 1/5& 2-3/5\\2-3/5 &5-9/5\end{vmatrix} = 3 > 0. $$

Since $\tilde{A}$ is positive definite, then $\lVert \tilde{x} \rVert_{\tilde{A}} = \sqrt{\tilde{x}^\top \tilde{A} \tilde{x}}$ is a norm, and thus convex.

$f(x)=\sqrt{x^TAx+b^Tx+c}$ is convex where $x^TAx+b^Tx+c\geq0$

$A$ should be assumed positive definite (e.g., $\sqrt{25-x^2}$ is not convex on $[0,5]$).

Proof

Some nonnegative polynomials can be written as a sum of squares. By Hilbert's Theorem, that is the case for every second degree polynomial. This allows you to write the function as a norm.

Failed attempt below

For convenience I assume that $A$ is symmetric. The gradient of $f$ is $$Df=\frac{2Ax + b}{2\sqrt{x^TAx+b^Tx+c}}$$ and the Hessian is: $$Hf =\frac{4\sqrt{x^TAx+b^Tx+c}A - (2Ax+b)(2Ax+b)^T/\sqrt{x^TAx+b^Tx+c}}{4(x^TAx+b^Tx+c)}$$ Multiplying the numerator and denominator with $\sqrt{x^TAx+b^Tx+c}$ yields: $$Hf =\frac{4(x^TAx+b^Tx+c)A - (2Ax+b)(2Ax+b)^T}{4(x^TAx+b^Tx+c)^{3/2}}$$ The denominator is positive on the interior of the feasible region, so all we need to check is if the numerator is positive semidefinite. In the one dimensional case, the numerator simplifies to $4ac-b^2$, which is indeed nonnegative because $ax^2+bx+c=0$ has at most one solution. Looking at derivations of the abc-formula, completing the square might be the key to a solution, but I do not yet see how it can be done. Another issue in higher dimensions is that $x^TAxA$ does not cancel against $Axx^TA$. Perhaps the statement is false after all.