[proofplan] One inclusion follows directly by adding the two subgradient inequalities. For the reverse inclusion, we turn $s \in \partial(f+g)(x)$ into the statement that $(x,x)$ minimizes a convex function on the diagonal constraint $y=z$. The relative-interior hypothesis is exactly the convex constraint qualification that gives a Lagrange multiplier for this diagonal constraint. That multiplier separates the contribution of $f$ from the contribution of $g$, producing $s = s_f+s_g$ with $s_f \in \partial f(x)$ and $s_g \in \partial g(x)$. [/proofplan] [step:Add the two subgradient inequalities to get the easy inclusion] Let $x \in \operatorname{dom} f \cap \operatorname{dom} g$. Let $u \in \partial f(x)$ and $v \in \partial g(x)$. By the definition of the subdifferential, for every $y \in \mathbb{R}^n$, \begin{align*} f(y) \geq f(x) + u \cdot (y-x) \end{align*} and \begin{align*} g(y) \geq g(x) + v \cdot (y-x). \end{align*} Adding these two inequalities gives, for every $y \in \mathbb{R}^n$, \begin{align*} (f+g)(y) \geq (f+g)(x) + (u+v)\cdot (y-x). \end{align*} Thus $u+v \in \partial(f+g)(x)$, and therefore \begin{align*} \partial f(x)+\partial g(x) \subset \partial(f+g)(x). \end{align*} [/step] [step:Convert a subgradient of the sum into a constrained convex minimization problem] Let $s \in \partial(f+g)(x)$. Define the convex function $F: \mathbb{R}^n \times \mathbb{R}^n \to (-\infty,\infty]$ by \begin{align*} F(y,z) := f(y)+g(z)-s\cdot y. \end{align*} Let $L := \{(y,z) \in \mathbb{R}^n \times \mathbb{R}^n : y=z\}$ be the diagonal linear subspace. Since $s \in \partial(f+g)(x)$, for every $y \in \mathbb{R}^n$, \begin{align*} f(y)+g(y)-s\cdot y \geq f(x)+g(x)-s\cdot x. \end{align*} Equivalently, $(x,x)$ minimizes $F$ over $L$. The constraint qualification holds because \begin{align*} \operatorname{ri}(\operatorname{dom} F) = \operatorname{ri}(\operatorname{dom} f) \times \operatorname{ri}(\operatorname{dom} g) \end{align*} and the hypothesis gives a point $a \in \operatorname{ri}(\operatorname{dom} f) \cap \operatorname{ri}(\operatorname{dom} g)$, so $(a,a) \in \operatorname{ri}(\operatorname{dom} F) \cap L$. [/step] [step:Use the diagonal multiplier to separate the two summands] By the finite-dimensional convex Lagrange multiplier theorem under the relative-interior constraint qualification, applied to the proper convex function $F$ and the affine constraint $L$, there exists a vector $\lambda \in \mathbb{R}^n$ such that, for every $(y,z) \in \mathbb{R}^n \times \mathbb{R}^n$, \begin{align*} F(y,z) \geq F(x,x) - \lambda\cdot(y-x) + \lambda\cdot(z-x). \end{align*} Here the multiplier vector for the diagonal constraint has the form $(-\lambda,\lambda)$ because the orthogonal complement of $L$ is \begin{align*} L^\perp = \{(-\lambda,\lambda) : \lambda \in \mathbb{R}^n\}. \end{align*} This use of the multiplier theorem is the only external convex-analytic ingredient in the proof; it is the standard finite-dimensional separation theorem for a convex epigraph and an affine constraint under relative-interior feasibility. [guided] We now explain carefully why the multiplier has exactly the form needed to split $s$. The subgradient assumption says that $x$ minimizes the function $y \mapsto f(y)+g(y)-s\cdot y$. To separate the two summands, we introduce two independent variables $y$ and $z$ and impose the diagonal constraint $y=z$. Thus we work with the convex function $F: \mathbb{R}^n \times \mathbb{R}^n \to (-\infty,\infty]$ defined by \begin{align*} F(y,z) := f(y)+g(z)-s\cdot y. \end{align*} The diagonal constraint is the linear subspace \begin{align*} L := \{(y,z) \in \mathbb{R}^n \times \mathbb{R}^n : y=z\}. \end{align*} On this subspace, $F(y,y)=f(y)+g(y)-s\cdot y$, so the condition $s \in \partial(f+g)(x)$ says exactly that $(x,x)$ minimizes $F$ over $L$. The relative-interior hypothesis is needed to rule out abnormal separation. Since $\operatorname{dom} F=\operatorname{dom} f \times \operatorname{dom} g$, the relative interior of the product is \begin{align*} \operatorname{ri}(\operatorname{dom} F)=\operatorname{ri}(\operatorname{dom} f)\times \operatorname{ri}(\operatorname{dom} g). \end{align*} Choose $a \in \operatorname{ri}(\operatorname{dom} f)\cap \operatorname{ri}(\operatorname{dom} g)$. Then $(a,a)\in \operatorname{ri}(\operatorname{dom} F)\cap L$, so the finite-dimensional convex Lagrange multiplier theorem under relative-interior feasibility applies. It gives a vector in the orthogonal complement $L^\perp$ that supports $F$ at the constrained minimizer $(x,x)$. We compute this orthogonal complement explicitly. A vector $(p,q)\in \mathbb{R}^n\times\mathbb{R}^n$ belongs to $L^\perp$ precisely when \begin{align*} p\cdot y+q\cdot y=0 \end{align*} for every $y\in\mathbb{R}^n$. This is equivalent to $p+q=0$, so every element of $L^\perp$ has the form $(-\lambda,\lambda)$ for a unique $\lambda\in\mathbb{R}^n$. Therefore the multiplier theorem gives a vector $\lambda\in\mathbb{R}^n$ such that, for every $(y,z)\in\mathbb{R}^n\times\mathbb{R}^n$, \begin{align*} F(y,z)\geq F(x,x)-\lambda\cdot(y-x)+\lambda\cdot(z-x). \end{align*} This inequality is the mechanism that will split the single subgradient $s$ into one part assigned to $f$ and one part assigned to $g$. [/guided] [/step] [step:Read off the two separate subgradient inequalities] Expanding the multiplier inequality gives, for every $y,z \in \mathbb{R}^n$, \begin{align*} f(y)+g(z)-s\cdot y \geq f(x)+g(x)-s\cdot x-\lambda\cdot(y-x)+\lambda\cdot(z-x). \end{align*} Set $z=x$. Since $g(x)<\infty$, subtracting $g(x)$ gives, for every $y \in \mathbb{R}^n$, \begin{align*} f(y) \geq f(x)+(s-\lambda)\cdot(y-x). \end{align*} Hence $s-\lambda \in \partial f(x)$. Set $y=x$. Since $f(x)<\infty$, subtracting $f(x)$ gives, for every $z \in \mathbb{R}^n$, \begin{align*} g(z) \geq g(x)+\lambda\cdot(z-x). \end{align*} Hence $\lambda \in \partial g(x)$. [/step] [step:Combine the two inclusions] The previous step gives \begin{align*} s=(s-\lambda)+\lambda \end{align*} with $s-\lambda \in \partial f(x)$ and $\lambda \in \partial g(x)$. Therefore $s \in \partial f(x)+\partial g(x)$. Since $s \in \partial(f+g)(x)$ was arbitrary, \begin{align*} \partial(f+g)(x) \subset \partial f(x)+\partial g(x). \end{align*} Together with the first inclusion, this proves \begin{align*} \partial(f+g)(x)=\partial f(x)+\partial g(x) \end{align*} for every $x \in \operatorname{dom} f \cap \operatorname{dom} g$. [/step]