Is there a simple proof that Kirchhoff's circuit laws always provide an exactly complete set of equations? Suppose I have a complicated electric circuit which is composed exclusively of resistors and voltage and current sources, wired up together in a complicated way. The standard way to solve the circuit (by which I mean finding the voltage across, and current through, each circuit element) is to formulate Kirchhoff's laws for both current and voltage, and these will yield linear equations which enable one to solve for all the relevant quantities.
However, there are two problems with these laws:


*

*There are too many of them. For example, in the simple circuit below, there are three different possible loops one can draw, but only two independent voltages. Similarly,

*The equations are not all independent. In the circuit below, the current conservation equations for the two different nodes turn out to be exactly the same equation.

Fortunately, in real life, these problems happen to exactly cancel out, and one gets exactly the correct number of equations to solve the circuit. There are never too many contradicting constraints (the linear system is never overdetermined) and there are always enough equations to pin everything down (the linear system is never underdetermined).
Why is this? Is there a simple proof of this fact? What are the fundamental reasons for it?
 A: 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.
A: 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?
A: 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.
A: 
there are always enough equations to pin everything down (the linear
  system is never underdetermined).

Here's a simple ideal circuit, consisting of a voltage controlled current source (VCCS) and a resistor, where the resistor current $I_R$ is undetermined by the circuit equations:

The voltage across the resistor (top terminal is positive) is given by Ohms law:
$$V_R = I_R\cdot 1\Omega$$
The VCCS control voltage equals $V_R$ by KVL, and the resistor current equals the VCCS current by KCL. Thus, the resistor current is given by
$$I_R = V_R \cdot 1\mho$$
and so the circuit equations yield
$$ I_R = I_R\cdot 1\Omega\cdot 1\mho = I_R$$
That is, any value for $I_R$ solves this circuit.

Update to address this comment:

The question lists what components are allowed. A VCCS isn't one of
  them. – Ben Crowell 1 hour ago

In fact, the question lists (1) resistors, (2) voltage sources, and (3) current sources as the allowed components according to the opening sentence:

Suppose I have a complicated electric circuit which is composed
  exclusively of resistors and voltage and current sources...

Now a VCCS is a current source. The term "current source", unqualified with either independent or dependent (controlled), may refer to either type.

An ideal current source generates a current that is independent of the
  voltage changes across it. ... If the current
  through an ideal current source can be specified independently of any
  other variable in a circuit, it is called an independent current
  source. Conversely, if the current through an ideal current source is
  determined by some other voltage or current in a circuit, it is called
  a dependent or controlled current source.

It may be that Emilio is only interested in circuits with independent sources for this question. But it certainly isn't the case that the question explicitly states that, nor is it the case that one could rationally conclude that dependent sources are obviously excluded from consideration.
So, unless and until Emilio edits his question to explicitly state that only circuits with resistors and independent sources are to be considered, I will leave this answer as is. 
A: The second problem solves the first one. If enough data are known from measurement, then the state of the system is determined uniquely. If more than enough data were measured this will not impact the solution, unless of course Kirchhoff's assumptions are not met or Maxwell's equations are flawed.
As to the requested fundamental reasons, Kirchhoff's laws follow directly from Maxwell's equations, which imply current conservation and the vanishing of ${\bf \nabla} \times {\bf E} $ under Kirchhoff's assumptions. 
