Given n+1 (x,y) data pairs, with all x values being unique, then a polynomial of order n or less passes thru the (n+1) data points. How can we prove that this polynomial is unique?
I am going to show you the proof for a particular case and you can extend it to polynomials of any order n.
Lets suppose you are given three data points (x1,y1), (x2,y2), (x3,y3) where x1 
Then if a polynomial P(x) of order 2 or less passes thru the three data points, we want to show that P(x) is unique.
We will prove this by contradiction.
Let there be another polynomial Q(x) of order 2 or less that goes thru the three data points. Then R(x)=P(x)-Q(x) is another polynomial of order 2 or less. But the value of P(x) and Q(x) is same at the three x-values of the data points x1, x2, x3. Hence R(x) has three zeros, at x=x1, x2 and x3.
But a second order polynomial only has two zeros; the only case where a second order polynomial can have three zeros is if R(x) is identically equal to zero, and hence have infinite zeros. Since R(x)=P(x)-Q(x), and R(x) 
But how do you know that a second oder polynomial with three zeros is identically zero.
R(x) is of the form a0+a1*x+a2*x^2 and has three zeros, x1, x2, x3. Then it needs to satisfy the following three equations
a0+a1*x1+a2*x1^2=0
a0+a1*x2+a2*x2^2=0
a0+a1*x3+a2*x3^2=0
The above equations have the trivial solution a0=a1=a2=0 as the only solution if
det(1 x1 x1^2; 1 x2 x2^2; 1 x3 x3^2)
That is in fact the case as
det(1 x1 x1^2; 1 x2 x2^2; 1 x3 x3^2) = (x1-x2)*(x2-x3)*(x3-x1),
and since x1
det(1 x1 x1^2; 1 x2 x2^2; 1 x3 x3^2)
So the only solution is a0=a1=a2=0 making R(x)
This post brought to you by Holistic Numerical Methods: Numerical Methods for the STEM undergraduate at http://numericalmethods.eng.usf.edu
The Numerical Methods Guy 