This answer is adapted from Problem 1.4 in Používáme lineární algebru, a book of solved problems in linear algebra (freely accessible online but unfortunately only in Czech, AFAIK). I will show that with the following assumptions:
- We deal with a DC or (low-frequency) AC circuit whose only elements are resistors and ideal voltage sources,
- Every edge of the circuit carries nonzero (positive) resistance,
Kirchhoff's circuit laws give a unique solution for the current and voltage on every element of the circuit.
First some comments. The uniqueness is easy to understand on physical grounds. Linearity of Kirchhoff's laws implies that there can only be more than one solution if the same circuit with the sources removed (i.e. their voltage set to zero without changing the topology of the circuit) can support nontrivial currents. The assumption of positive resistance of every edge of the circuit makes this physically impossible due to energy conservation. For the same reason, I believe the same statement holds for AC circuits with other elements than resistors as long as the impedance of every edge has a positive real part. It is however not immediately obvious to me how the below argument generalizes to this case. One can also easily see that dropping the assumption of positive resistance may lead to both ambiguities in the solution and pathologies: see the answers by Ryan Hazelton and Alfred Centauri. Finally, the same argument should apply to circuits with ideal current sources due to the duality between the two types of sources; the assumption of ideal voltage sources is just for simplicity of notation.
Now to the business. I will assume WLOG that the circuit is represented by a connected graph; otherwise one simply considers all connected components one by one. The argument essentially follows the node-voltage method. In the first step, we realize that Kirchhoff's second (voltage) law is equivalent to the existence of a potential on the graph. Suppose that the circuit has $N$ vertices (nodes). We can choose the potential of one of them arbitrarily, say $u_1=0$. For a given solution of Kirchhoff's laws, we can then obtain the potential $u_i$ of the $i$-th vertex by adding up voltage drops over resistors and voltages delivered by sources over any path connecting the $i$-th vertex to $u_1$. Kirchhoff's second law guarantees that the result for $u_i$ is independent of the choice of the path, and thus well-defined.
In the second step, we deal with a set of equations for the unknown potentials $u_2,\dotsc,u_N$, implied by Kirchhoff's first (current) law. We only consider vertices $2,\dotsc,N$, which gives $N-1$ equations for the $N-1$ unknown potentials. The equation for the $i$-th vertex reads symbolically
$$
\sum_j\frac1{R_{ij}}(u_i-u_j+U_{ij})=0,
$$
where the sum is over all vertices $j$ connected to $i$ by an edge, $R_{ij}$ denotes the resistance in the edge $ij$, and $U_{ij}$ the voltage delivered by sources therein. We can write this set of equations in the matrix form, $M\vec u=\vec U$, where $\vec u=(u_2,\dotsc,u_N)^T$ and $\vec U$ contains the source data. The diagonal elements of the matrix $M$ are
$$
M_{ii}=\sum_j\frac1{R_{ij}},
$$
whereas the offdiagonal elements are
$$
M_{ij}=
\begin{cases}
-1/R_{ij}\text{ if $i$ and $j$ are connected and $j\neq1$,}\\
0\text{ otherwise.}
\end{cases}
$$
The positivity of all the resistances implies that
$$
\sum_{j\neq i}|M_{ij}|\leq|M_{ii}|
$$
for all $i=2,\dotsc,N$. Moreover, there are such $i$ (those connected by an edge to $u_1$) for which the strict inequality holds. This implies that the matrix $M$ is diagonally dominant, and hence invertible. This guarantees that the set of equations for the potentials $u_2,\dotsc,u_N$ has a unique solution.
Once all the potentials are known, the currents through all the edges of the circuit are easily reconstructed. The current through the edge $ij$ is, symbolically,
$$
I_{ij}=\frac1{R_{ij}}(u_i-u_j+U_{ij}).
$$
This concludes the argument, and shows mathematically why the assumption of positive resistances is a sufficient condition for establishing the existence of a unique solution. More generally, a unique solution exists whenever the above-defined matrix $M_{ij}$, which depends on the topology of the circuit and the resistances but not on the sources, is nonsingular. Should $M_{ij}$ be singular, there can be more than one solution, or no solutions at all, as known from linear algebra.
EDIT: In response to the comments by Titti, here are some more details justifying why the matrix $M$ is invertible. From the corresponding Wikipedia page, a matrix is invertible if (i) it is diagonally dominant, (ii) the sharp inequality (strict diagonal dominance) holds at least for one diagonal element, and (iii) it is irreducible. The first two conditions are explicitly verified above. Irreducibility means that the indices cannot be partitioned into two sets $I,J$ such that $M_{ij}=0$ for all $i\in I$ and $j\in J$. Should the matrix $M$ be reducible, then the nodes of the circuit corresponding to the sets $I$ and $J$ would necessarily be disconnected, unless our circuit consists of two subcircuits that are only "touching" at vertex 1. But such subcircuits can always be treated as separate. With the assumption that the circuit is connected, the condition (iii) can therefore also be considered satisfied.
