Consider the incidence $n\times n$ matrix of this graph - where the rows are the students, the columns are the classes, and the entry at row $i$ and column $j$ is $1$ if student $i$ is enrolled in class $j$, and $0$ otherwise. The statement says that the $n$ rows are pairwise distinct, and asks to prove that we can eliminate some column, such that the rows of the remaining $n\times (n-1)$ matrix remain pairwise distinct. As such it's quite an old chestnut - discussed for example in a book by Ross Honsberger, where he presents a graph theoretical solution by a "brilliant" Bulgarian mathematician. An (apparently) more general problem, for a $n\times m$ matrix with $m\geq n$, states that we can eliminate some $m-n+1$ columns, and can readily be proved by induction. Notice that for $m=n-1$ it might be the case that no column can be eliminated, for example for the matrix $\begin{bmatrix} 0 & 0 & \cdots & 0 & 0 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ 0 & 0 & \cdots & 0 & 1 \\\end{bmatrix}$.

Do you know were can I find the solution? Or can you please post a solution?

Here's what might be the graph theoretical solution referenced in the above post. Construct a graph of $n$ vertices representing the students. If two students would be given exactly the same schedules by the closure of class $i$ (where $i \in \{1, 2, \ldots, n\}$), draw an edge of color $i$ between those two vertices. Note two vertices can have at most one edge between them. We want to show one edge color is not represented. Suppose all colors are represented. Arbitrarily cross out edges until exactly one edge of each color remains. This leaves a graph with $n$ vertices and $n$ edges. This graph has a cycle. But try to follow that cycle all the way around. That means we start with a student's schedule, toggle some classes, and somehow end up with the schedule we started with, despite all the toggles being distinct. Contradiction.

In an $n\times n$ array of numbers all rows are different (two rows are different if they differ in at least one entry). Prove that there is a column which can be deleted in such a way that the remaining rows are still different. We prove by induction on $k$ the following statement: at least $n-k+1$ columns can be deleted in such a way that the first $k$ rows are still different. For $k=2$ the assertion is true. Indeed, the first two rows differ in at least one place, so we can delete the remaining $n-1$ columns. Suppose the assertion is true for $k,$ that is we can delete $n-k+1$ columns and the first $k$ rows are still different. If after the deletion of the columns the $(k+1)$-th row is different from all first $k$ rows, we can put back any of the deleted columns and remain with $n-k$ deleted columns and $k+1$ different rows. If after the deletion the $(k+1)$-th row coincides with one of the first rows, then we put back the column in which the two rows differ in the original array. For $k=n$ we obtain the desired result.

In an $n\times n$ array of numbers all rows are different (two rows are different if they differ in at least one entry). Prove that there is a column which can be deleted in such a way that the remaining rows are still different. Assume on the contrary, for each $i\,,\,i=1,2,\ldots,n $ there exist two rows $a, b$ (depending on $i$) which are equal except for the $i$-th position and obviously they differ at that position. We denote it as $a =(i)\, b$. Since we have $n$ such connections between $n$ rows, there will be a "cycle": \[ a_1 =(i_1)\, a_2 =(i_2)\, a_3 =(i_3)\, \ldots =(i_{k-2})\, a_{k-1}=(i_{k-1})\, a_{k}\,,\, a_{k}=(i_{k})\, a_1 \] Now, the first chain means the rows $a_1$ and $a_k$ are equal except for the positions at $i_1, i_2,\ldots, i_{k-1}$, whence they are equal at the column $i_k$. But, $a_{k}=(i_{k})\,a_1$ contradicts to it. Comment. In fact, as appears, it's essentially the same idea as MellowMelon's with different wording. I also like enescu's solution, since it is a constructive one.

enescu wrote: If after the deletion of the columns the $(k+1)$-th row is different from all first $k$ rows, we can put back any of the deleted columns and remain with $n-k$ deleted columns and $k+1$ different rows. Why?

Takeya.O wrote: enescu wrote: If after the deletion of the columns the $(k+1)$-th row is different from all first $k$ rows, we can put back any of the deleted columns and remain with $n-k$ deleted columns and $k+1$ different rows. Why? Because the first $k+1$ rows are already different in the $k-1$ columns that were not deleted, but different rows stay different when an extra column is added back in. I like enescu's solution a lot; it doesn't rely on any graph theory or ideas about cycles. Note that it can be made even slicker by starting the induction at $k=1$ instead of at $k=2$. EDIT: The same exercise has been discussed at https://artofproblemsolving.com/community/c6h5941 . An old chestnut indeed!

For example, After the deletion, we get $12$ $11$ If we add column $2$ $3$ ,then the two rows coincide. Please teach me.

Takeya.O wrote: For example, After the deletion, we get $12$ $11$ If we add column $2$ $3$ ,then the two rows coincide. I don't understand. If we add your column, then we obtain the two rows $122$ $113$ which surely don't coincide!

I have thinked that two rows coincide is equivalent to the sums of numbers is equal. Thanks, Mr.darij