  We derive a number of upper and lower bounds for the first nontrivial
eigenvalue of a finite quantum graph in terms of the edge connectivity of the
graph, i.e., the minimal number of edges which need to be removed to make the
graph disconnected. On combinatorial graphs, one of the bounds is the
well-known inequality of Fiedler, of which we give a new variational proof. On
quantum graphs, the corresponding bound generalizes a recent result of Band and
L\'evy. All proofs are general enough to yield corresponding estimates for the
$p$-Laplacian and allow us to identify the minimizers.
  Based on the Betti number of the graph, we also derive upper and lower bounds
on all eigenvalues which are "asymptotically correct", i.e. agree with the Weyl
asymptotics for the eigenvalues of the quantum graph. In particular, the lower
bounds improve the bounds of Friedlander on any given graph for all but
finitely many eigenvalues, while the upper bounds improve recent results of
Ariturk. Our estimates are also used to derive bounds on the eigenvalues of the
normalized Laplacian matrix that improve known bounds of spectral graph theory.
