In this paper, we establish Betti number estimates for graphs with non-negative Ollivier curvature, and for graphs with non-negative Bakry-Émery curvature, providing a discrete analogue of a classical result by Bochner for manifolds. Specifically, we show that for graphs with non-negative Ollivier curvature, the first Betti number is bounded above by half of the minimum combinatorial vertex degree. In contrast, for graphs with non-negative Bakry-Émery curvature, we prove that the first Betti number of the path homology is bounded above by the minimum combinatorial vertex degree minus one. We further present various rigidity results, characterizing graphs that attain the upper bound on the first Betti number under non-negative Ollivier curvature. Remarkably, these graphs are precisely the discrete tori, similar to the Riemannian setting. Furthermore, we show that the results obtained using the Ollivier curvature extend to the setting of potentially non-reversible Markov chains. Additionally, we explore rigidity cases depending on the idleness parameter of the Ollivier curvature, i.e., we characterize rigidity for bone-idle graphs with non-negative Ollivier curvature that attain the upper Betti number bound. We further establish an upper bound on the first Betti number under a more general assumption, where non-negative Ollivier curvature is required only outside a finite subset. Finally, we provide several examples, e.g., we prove that for a potentially non-reversible Markov chain on a cycle of length at least five, there always exists a unique path metric with constant Ollivier curvature. Moreover, this metric has non-negative Ollivier curvature, and the upper Betti number bound is attained if and only if the curvature is zero.