## 3 Characteristics of OS Graphs
\(\square\)  
**Theorem 8**. : _In \(O(n)\), if \(V(P_{k})=V(P_{i})=2\), then \(P_{k}\) cannot be connected to \(P_{i}\)._  
**Proof**. If \(P_{k}\) is connected to \(P_{i}\), then, according to axiom d, there exists a mediator vertex, \(P_{m}\), connected to both \(P_{k}\) and \(P_{i}\). Let \(V(P_{m})=x\); then, SS(P\({}_{k})=2\),\(x\). SS(P\({}_{1})=2\),\(x\)., so that \(P_{k}=P_{i}\), in contradiction to axiom e. \(\square\)  
**Theorem 9**. : _If \(m_{n-1}=1\), then \(m_{2}\leq minl(n-1)/2\), \(I-2\)._  
**Proof**. Let set (a) be the set of all the \(m_{2}\) vertices having \(V=2\) and (b) be the set of all the other n-\(m_{2}\) vertices. Every vertex of (a) has to be connected to \(2\) vertices of (b) according to Theorem 8. Now, if \(m_{n-1}=1\), then every vertex of (a) must be connected to the vertex \(P_{n-1}\), having \(V=n-1\), so that the number of possibilities of choosing the second vertex of the pair is \(n-m_{2}-1\), and so that \(m_{2}\leq n-m_{2}-1\) or \(m_{2}\leq(n-1)/2\). Also, every vertex of set (a) must be connected to a vertex with different valency of set (b) (since it is already connected to the vertex having valency equal to \(n-1\)). The number of such subsets of vertices with different valency, excluding \(P_{n-1}\), which is a subset of its own and the subset of vertices having \(V=2\), is \(I-2\), so that \(m_{2}\leq I-2\). Hence, \(m_{2}\leq minl(n-1)/2,I-2\). \(\square\)  
**Theorem 10**. : _In \(O(n)\), if \(V(P)=3\) and \(P\) is connected to the vertices \(P_{1}\), \(P_{2}\), and \(P_{3}\), then one of these vertices, say \(P_{2}\), has to be connected to the other two and satisfy the condition \(v(P_{2})>3\)._  
**Proof**. According to axiom d, if \(P_{1}\) is connected to \(P\), then there must be another vertex connected to \(P\) and \(P_{1}\). Let this vertex be \(P_{2}\). The same goes for \(P_{3}\), which must be connected either to \(P_{1}\) or to \(P_{2}\). Hence, there is a vertex (from \(P_{1}\), \(P_{2}\), and \(P_{3}\)) connected to the other two. Now, if this vertex is \(P_{2}\) and \(V(P_{2})=3\), then SS(P) = SS(P\({}_{2})=3\),\(x\),y, where \(x=V(P_{1})\) and \(y=V(P_{3})\), and \(P=P_{2}\). So, there exists at least one other vertex connected to \(P_{2}\); hence, \(V(P_{2})>3\). \(\square\)  
**Theorem 11**. : _In \(O(n)\), if \(V(P)=3\), then \(P\) cannot be connected to more than one vertex having \(V=2\)._  
Proof. : Suppose that P is connected to P\({}_{1}\), P\({}_{2}\), and P\({}_{3}\) and let V(P\({}_{1}\)) = V(P\({}_{3}\)) = 2 and V(P\({}_{2}\)) = x \(>\) 3 (according to the previous theorem). According to Theorem 10, the only possible connection of P to P\({}_{1}\), P\({}_{2}\), and P\({}_{3}\) satisfies SS(P\({}_{1}\)) = SS(P\({}_{3}\)) = 3,x. So, P\({}_{1}\) = P\({}_{3}\), in contradiction to axiom e. \(\square\)  
**Theorem 12**. : _If V(P) = 2, then \(P\) cannot be connected to more than one vertex having \(V=3\)._  
Proof. : Let P be connected to P\({}_{1}\) and P\({}_{2}\), and V(P\({}_{1}\)) = V(P\({}_{2}\)) = 3. According to axiom d, P\({}_{1}\) and P\({}_{2}\) have to be connected to each other, since if P and P\({}_{1}\) are connected, there must be a vertex connected to both, but since V(P) = 2, this third vertex must be P\({}_{2}\). According to Theorem 10, P\({}_{1}\) has to be connected to P\({}_{3}\), having V = x \(>\) 3. However, since P\({}_{1}\) and P\({}_{3}\) are connected, then according to axiom d, there must be a third vertex connected to both. Now, since P\({}_{1}\) already has three connections (P, P\({}_{2}\), and P\({}_{3}\)), no additional vertex can be connected to P\({}_{1}\); hence, this mediator can be either P or P\({}_{2}\). However, P has two connections already and can have no more. Thus, P\({}_{3}\) must be connected to P\({}_{2}\) so that SS(P\({}_{1}\)) = SS(P\({}_{2}\)) = 2,3,x, in contradiction to axiom e. \(\square\)  
**Theorem 13**. : _There cannot exist an OS of the order \(n=3\)._  
Proof.