MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Here is an example I learned about this month: The edges of the complete graph cannot be partitioned into fewer than $n-1$ complete bipartite graphs. Apparently the only known proofs involve linear algebra.