# Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?

Consider the Traveling Salesman Problem: Input: $$n$$ cities, distances $$c_{ij}$$ for each ordered pair $$(i,j)$$ of them.

Output: Find a shortest round tour visiting every city exactly once.

I came across the following ILP formulation, where we introduce a variable $$x_{ij} \in \{0,1\}$$ for each pair of cities $$i,j$$ where $$x_{ij} = 1$$ means arc $$i,j$$ is part of the tour. Then we have:

Minimize $$\sum_{1 \leq i,j \leq n} c_{ij} x_{ij}$$

Subject to $$\forall k = 1, \dots, n: \sum_{1 \leq i \leq n} x_{ik} = 1$$ $$\forall k= 1, \dots, n: \sum_{1 \leq j \leq n} x_{kj} = 1$$ $$\forall \subsetneq S \subsetneq \{1, \dots, n\}: \sum_{i,j \in S} x_{ij} \leq |S| -1$$

While I understand the purpose of the first two constraints to make sure there is only one incoming and one outgoing edge per city, I do not understand the purpose of the third constraint. From what I read, this constraint is to make sure that solutions consisting of several disconnected tours are not possible - But how is this enforced by the third constraint and why are disconnected subtours not prevented by the first two constraints already? If we have two disconnected subtours, then at least one vertex must have an incoming edge but no outgoing edge, no?

Every vertex has one incoming and one outgoing edge, so it is not prevented by the first two constraints. It is however prevented by the third constraint, as if you take any of the two connected components for $$S$$ it violates the inequality.