  The vertex (resp. edge) metric dimension of a connected graph G; denoted by
dim(G) (resp. edim(G)), is defined as the size of a smallest set S in V (G)
which distinguishes all pairs of vertices (resp. edges) in G: Bounds dim(G) <=
L(G)+2c(G) and edim(G) <= L(G) + 2c(G); where c(G) is the cyclomatic number in
G and L(G) depends on the number of leaves in G, are known to hold for cacti
and are conjectured to hold for general graphs. In leafless graphs it holds
that L(G) = 0; so for such graphs the conjectured upper bound becomes 2c(G). In
this paper, we show that the bound 2c(G) cannot be attained by leafless cacti,
so the upper bound for such cacti decreases to 2c(G)-1, and we characterize all
extremal leafless cacti for the decreased bound. We conjecture that the
decreased bound holds for all leafless graphs, i.e. graphs with minimum degree
at least two. We support this conjecture by showing that it holds for all
graphs with minimum degree at least three and that it is suficient to show that
it holds for all 2-connected graphs, and we also verify the conjecture for
graphs of small order.
