Is there a simple proof that Kirchhoff's circuit laws always provide an exactly complete set of equations?

The answer is not quite simple, to show this we need some graph theory and matrices. There is a beautiful document explaining this relation in detail:

Graphs, matrices, and circuit theory. Takis Konstantopoulus, February 2000.

Available at Semantic Scholar; original link at Uppsala University (now dead; archived version).

I think the "fundamental reason" of this is related with the fact that every loop have different variables, if we can generate a loop using another loop the equations will not be independent, of course this is my opinion, all the math is in the document.

Here's a counterexample:

Suppose two identical, ideal batteries (with zero internal resistance) are both connected in parallel across a single resistor; equivalently, replace one of the resistors in your diagram with a second, identical battery. Also assume the conducting wires are ideal (again, no resistance).

Kirchhoff's laws in this case result in an underdetermined system. If the current through the single resistor is I and the voltage across both ideal batteries is V, you cannot find the current through either battery using Kirchoff's laws alone; both loops give the voltage across the resistor as V, and both junctions say the sum of the currents through the batteries must equal I, but do not allow you to calculate either of those currents. For instance, a current of 3 I up through one battery and 2 I down through the other satisfies the system of equations. In this case you have to use a symmetry argument to conclude the current through each battery is I/2.

This is not a problem using real-world equipment, though, as voltage sources always have some amount of associated internal resistance. So if we agree to use non-ideal circuit elements, then I agree with the answer @Hu provided.

This indirectly raises another question; are Kirchoff's laws meaningful in ideal circuits? I'm sure there are many more examples like the one above, where the resulting system of linear equations is underdetermined (though I doubt there are cases which are overdetermined). We use ideal situations to model real systems, but is that a good idea when answers are undetermined in the ideal case?

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.