The sum of two algebraic integers of degree $2$ is an algebraic integer of degree $2$ or $4$, right? For example, $$(1 + \sqrt{2}) + (2 + \sqrt{2}) = 3 + 2 \sqrt{2},$$ so the result of that addition is also an algebraic integer of degree $2$. If instead we have $$(1 + \sqrt{2}) + (2 + i) = 3 + \sqrt{2} + i,$$ which has $x^4 - 12x^3 + 52x^2 - 96x + 72$ for a minimal polynomial, so it has degree $4$.
That's all I've tried: adding up seemingly random algebraic integers of degree $2$. In doing this, I haven't found algebraic integers of degree $3$ or degree $5$ or higher. Are there such numbers to be found?
 A: In the case of quadratic fields, things can be made more precise. Given two  algebraic numbers $\alpha, \beta$ of degree 2, introduce, as @Mathmo123 does, the quadratic fields $\mathbf Q(\alpha), \mathbf Q(\beta)$. Since $\alpha, \beta$ are roots of polynomials of degree 2 in $\mathbf Q [X]$, everybody knows that $\mathbf Q(\alpha)=\mathbf Q(\sqrt A), \mathbf Q(\beta)=\mathbf Q(\sqrt B)$, where $A, B$ are the respective discriminants. The advantage of "pure" quadratic fields is that $A, B$ can be chosen to be square free integers, and then $\mathbf Q(\sqrt A)=\mathbf Q(\sqrt B)$ if and only if $A=B$ (check!). If $\mathbf Q(\alpha)=\mathbf Q(\beta)$, obviously $\alpha+ \beta$ has degree 2.
Suppose now that $\mathbf Q(\sqrt A)\neq\mathbf Q(\sqrt B)$. The biquadratic field  $K=\mathbf Q(\alpha, \beta)$ has exactly three quadratic subfields, which are $\mathbf Q(\sqrt A),\mathbf Q(\sqrt B), \mathbf Q(\sqrt {AB})$, and $\alpha + \beta$ has degree 2 if and only if it belongs to one of these subfields. The only possible case is that $\alpha + \beta \in \mathbf Q(\sqrt {AB}) (*)$. Let us show that it cannot occur. Write $\alpha$, resp. $\beta$, resp. $\alpha + \beta$  as a $\mathbf Q$-linear combination of $1$ and $\sqrt A$, resp. $\sqrt B$, resp. $\sqrt {AB}$. The condition $(*)$ is then equivalent to a non trivial $\mathbf Q$-linear combination of $1,\sqrt A,\sqrt B,\sqrt {AB}$ which is null, contradicting the fact that  $1,\sqrt A,\sqrt B,\sqrt {AB}$ form a $\mathbf Q$-basis of $K$.
Summarizing : if $\mathbf Q(\alpha)\neq\mathbf Q(\beta)$,then  $\alpha+ \beta$ has degree 4.
A: Working with number fields is going to be much easier than working with polynomials. If $\alpha, \beta$ are algebraic integers of degree 2, then by definition,
$$[\mathbb Q(\alpha):\mathbb Q] = [\mathbb Q(\beta):\mathbb Q] = 2.$$
In particular, since 
$$[\mathbb Q(\alpha, \beta):\mathbb Q(\alpha)] \le [\mathbb Q(\beta):\mathbb Q] ,$$
it follows from the tower rule that $[\mathbb Q(\alpha, \beta):\mathbb Q]$ is either $2$ or $4$. 
But $\alpha + \beta \in \mathbb Q(\alpha, \beta)$. Hence, by the tower rule again, the degree of $\alpha + \beta$ must divide $4$.
This argument generalises to an arbitrary number of generators with arbitrary degrees.
