In this paper, we will develop a new method to study coupled fixed points of a mapping $T:X \times X \to X$, where $(X, d)$ is a special class of $b$-metric spaces endowed with a graph. We will prove some general fixed point theorems which enable us to extend some old results in fixed point theory. Moreover, we will extend Edelstein's fixed point theorem for two variable mappings in $\varepsilon$-chainable $b$-metric spaces.