Depth information is being widely used in many real-world applications. However, due to the limitation of depth sensing technology, the captured depth map in practice usually has much lower resolution than that of color image counterpart. In this paper, we propose to combine the internal smoothness prior and external gradient consistency constraint in graph domain for depth super-resolution. On one hand, a new graph Laplacian regularizer is proposed to preserve the inherent piecewise smooth characteristic of depth, which has desirable filtering properties. A specific weight matrix of the respect graph is defined to make full use of information of both depth and the corresponding guidance image. On the other hand, inspired by an observation that the gradient of depth is small except at edge separating regions, we introduce a graph gradient consistency constraint to enforce that the graph gradient of depth is close to the thresholded gradient of guidance. We reinterpret the gradient thresholding model as variational optimization with sparsity constraint. In this way, we remedy the problem of structure discrepancy between depth and guidance. Finally, the internal and external regularizations are casted into a unified optimization framework, which can be efficiently addressed by ADMM. Experimental results demonstrate that our method outperforms the state-of-the-art with respect to both objective and subjective quality evaluations.