# k-partite problem graph theory proof

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.

• Please explain a little more. You choose a node $u_1$ from the first partite set, is that right? And then you can choose a node $u_2$ from the second partite set, which is joined by an edge to $u_1,$ right? Now how do you know that you can choose a node from the third partite set, which is joined by edges to both $u_1$ and $u_2$? – bof May 15 '18 at 2:12
• Suppose the first column contains an Ace, a King, a Queen, and a Jack. Likewise the second column contains an Ace, a King, a Queen, and a Jack. So you choose an Ace from the first column and a King from the second column. But now the third column contains two Aces and two Kings! OOPS! So you have to look ahead somehow. – bof May 15 '18 at 2:14
• Here's a more natural way to model your problem with a graph. Consider a bipartite graph $K_{13,13}$ with $13$ nodes on each side. One one side there are nodes $c_1,c_2,\dots,c_{13}$ representing the $13$ columns of your array. On the other side are nodes $r_1,r_2,\dots,r_{13}$ representing the $13$ ranks in a deck of cards. Draw an edge $c_ir_j$ if column $i$ contains a card of rank $r_j$. Now your problem is to show that this graph has a perfect matching. Have you studied matchings in bipartite graphs? – bof May 15 '18 at 2:20
• Are you familiar with Hall's Marriage Theorem? If so, this gives a quick proof. If not, there is a proof along these lines: go from column to column, choosing arbitrary cards. If you get to a column whose ranks where already all chosen, then choose an arbitrary card, and have its choice "bump" the previous decisions. In effect, backtrack when you get stuck. You can show that this works. – Mike Earnest May 15 '18 at 2:21
• answered my own question. – B.Li May 15 '18 at 17:10

## 1 Answer

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.