Consider this problem:
In a deck of $52$ cards with $13$ ranks, each rank with $4$ cards, randomly place cards in a $4{\times}13$ matrix. Select one card from each column, prove there's always a way to select $13$ cards, with no two cards from the same rank.
I choose to do this with a graph theory proof:
Initiate a graph $G$ with $52$ nodes, each node representing an unique card. Add the edge $(u,v)$ to $G$ if $u$ and $v$ are not from the same rank. This by definition will create a 13-partite graph, with each partite set representing one of the $13$ ranks.
Each partite is by definition an independent set, and each node is connect to all other vertices not in the same partite, i.e. every node is connected to $4{\times}12$ other nodes.
For any edge $(u,v)$ in $G$, remove this edge if $u$ and $v$ are from the same column in the matrix. Each node will have at most $3$ removals. In the worse case, for each node, the $3$ edges removed are all from the same partite set in another partite. In other words, every node still have at least one edge to the other $12$ partite sets that are not its own, therefore, there's always a path of length $12$ that traverse all $13$ sets. Hence there's always a way to selected $13$ cards with no two cards from the same rank.
Is this a valid proof? I'm not sure if I missed something.
Via @bof and @Mike Earnest's comments, here's a proof with a more natural modeling:
Consider a bipartite graph $K_{13,13}$ with $13$ nodes on each side. Denote the vertices of one side by $C$, the $13$ column of the matrix, denote the other side by $R$, the $13$ ranks of the cards. Create an edge $(c_i,r_j)$ if column $i$ contains a card belonging to rank $j$ or vice versa.
Each vertex will have a degree of at least one. WLOG consider the set $C$, if $deg(c_i) = 1$, then $deg(N(c_i)) = 1$ as well. Since $deg(c_i) = 1$ means that the cards in column $i$ contains $4$ cards of the same rank. Now consider any subset $S\subseteq C$. We can see that the upper bound of $|S|$ is $\min (13, 4|S|)$, and the lower bound of $|N(S)|$ is therefore $\frac{4|S|}{4} = |S|$. Hence, by Hall's marriage theorem, $K_{13,13}$ has a perfect matching. Indeed, there's always a way to pick out $13$ cards of distinct rank from each column.