A Divided Kingdom

A kingdom has the shape of a convex $n$-sided polygon $A_1 \dots A_n$. The King owns a castle at point $O$ in the interior of the kingdom, and he has $n$ princes, $P_1, \dots P_n$. They are each given a castle at the vertices of the polygon, so that prince $P_i$ has a castle precisely at $A_i$. The area $OA_iA_{i+1}$ is called the province $i$.

One day, a strife breaks out in the kingdom and each prince declares independence from the King. As a result, each province is divided into one or more vassals, each of which is shaped like a triangle. (Note that each province is a triangle to begin with, so some of the more stable province do not necessarily break apart into multiple vassals). At the vertices of these triangles, a citadel (a smaller castle) was erected.

Each castle and fort then declares an allegiance to King or one of the princes while following these rules:
1. Each castle declares allegiance to its original owner. That is, castle at $O$ keeps its allegiance to the King and castle at $A_i$ keeps its allegiance to prince $P_i$.

2. Each citadel that lies in the province border declares allegiance to either one of the owner of the castles at the endpoints of the province border. For example, a citadel that lies in the line $A_1 A_2$ may declare allegiance to prince $P_1$ or $P_2$, and a citadel that lies in the line $OA_3$ may declare allegiance to either the King or prince $P_3$.

3. Each citadel that lies in the interior of a province declares an allegiance to either one of the owner of the castles at the vertices of the province. For example, a citadel that lies in the province 1 may declare allegiance to either the King, prince $P_1$, or prince $P_2$ (because province 1 is the triangle $OA_1A_2$).

Now, with all citadels and forts having declared allegiance, each vassal's ownership is resolved as follows. Note that each vassal is shaped like a triangle, so it has precisely three citadels or castles on the vertices. If two or more of those citadels or castles declare allegiance to an entity, then the vassal is owned by that entity. For example, if a vassal has vertices declaring allegiance to $P_1, P_2, P_1$, then that vassal is owned by prince $P_1$.

A vassal whose vertices declare allegiance to three different entities is then left in a constant state of war. Prove that the number of such vassals is $n+2k$ where $k$is a non-negative integer.