## 3 Characteristics of OS Graphs
: According to axioms a and d every vertex has to be connected to at least two other vertices so that all the three vertices in the graph have to be connected to each other. Hence the three vertices have the same valency = 2, and the same SS = 2,2. Thus, they are equal in contradiction to axiom e. \(\square\)  
**Theorem 14**. : _There cannot exist an OS of order \(n=4\)._  
Proof. : In this case, the valency of the vertices can be 2 or 3. According to Theorem 10, the existence of a vertex having V = 3 is impossible since it necessitates the existence of a vertex having V greater than 3. Hence, all vertices must have V = 2. But according to Theorem 8, the connections between these vertices cannot be realized. \(\square\)  
**Theorem 15**. : _There cannot exist an OS of order \(n=5\)._  
Proof. : Case 1: m\({}_{4}\) = 0. According to the Theorem 6, m\({}_{3}\)\(\leq\) 2. Also, m\({}_{2}\)\(\leq\) 1 because the only available connections for a vertex having V = 2 are to two vertices having V = 3 (see Theorem 8). So, m\({}_{2}\) + m\({}_{3}\) + m\({}_{4}\)\(\leq\) 3 is in contradiction to Theorem 3a, claiming that this sum should be equal to n = 5. Case 2: m\({}_{4}\) = 1. According to the Theorem 7, m\({}_{3}\)\(\leq\) 2. According to Theorem 9, m\({}_{2}\)\(\leq\) 1 - 2 = 1. (In this case I = 3 since there are three equivalent sets of vertices having V = 2,3,4.) Hence, m\({}_{2}\) + m\({}_{3}\) + m\({}_{4}\)\(\leq\) 1 + 2 + 1 = 4 \(<\) 5, in contradiction to Theorem 3(a). \(\square\)  
**Theorem 16**. : _There cannot exist an OS of the order \(n=6\)._  
Proof. : According to Theorem 4, m\({}_{5}\) = 0,1. Let us examine these two possibilities. **Case A**. \(m_{5}\) = 0. According to Theorems 8 and 12, the only possible SS for the vertices having V = 2 are 3,4 and 4,4, so that m\({}_{2}\)\(\leq\) 2. Let us show now that m\({}_{4}\)\(\
eq\) 0. Let us show now that \(m_{4}\
eq 1\). Since \(m_{4}\leq 3\) (Theorem 6), let us consider the case in which \(m_{4}=3\). According to Theorem 5, the only possible SS for the vertices having V = 4 are 4,4,2,2; 4,4,3,2; and 4,4,3,3. However, these three possibilities cannot be realized since, in this case, the OS will include seven vertices (having valences equal to 2, 2, 3, 3, 4, 4, and 4) instead of 6. Therefore, \(m_{4}\leq 2\). Since we proved that \(m_{4}\
eq 0,1\), there is only one possible value to \(m_{4}\), namely \(m_{4}=2\). Let us show now that \(m_{2}\
eq 0\). If \(m_{2}=0\), since \(m_{4}=2\), then \(m_{3}=4\) (Theorem 3(a)). But this is impossible since, according to Theorem 10, there are only three possible SSs for the vertices having V = 3: 4,4,4; 3,4,4; and 3,3,4. Therefore, since \(m_{2}\leq 2\), we obtain \(m_{2}=1,2\). We now show that \(m_{2}\
eq 1\), so that \(m_{2}=2\)  
If \(m_{2}=1\), then (since we found that \(m_{4}=2\)) \(m_{3}=6-2-1=3\). The handshaking lemma is a consequence of the degree sum formula, according to which the sum of the degrees (the numbers of times each vertex is touched) equals twice the number of edges N in the graph. Specifically, this means that, in the apriorics n = 6 case, we have the following (Theorem 3(b)):  
\[\sum_{i=2}^{5}i\,m_{i}=2N\]  
Since according to axiom d, \(m_{1}=0\) and according to axiom a, \(m_{0}=0\) this implies the following:  
\[3\,\,m_{3}+5\,m_{5}=even\]  
Now, this is in clear contradiction to \(m_{3}=3,\,\,m_{5}=0\); thus, this case cannot occur. So that \(m_{2}\
eq 1\). Since we found that \(m_{2}\leq 2\) and \(m_{2}\
eq 0\) we obtain \(m_{2}=2\). We have then to find an OS of order 6 having the following multiplicities: \(m_{5}=0\), \(m_{4}=2\), \(m_{2}=2\) and \(m_{3}=6-2-2=2\). Let the vertices of this OS be denoted as follows: P\({}_{1}\)(4), P\({}_{2}\)(4), P\({}_{3}\)(3), P\({}_{4}\)(3), P\({}_{5}\)(2), and P\({}_{6}\)(2)--see Figure 3-1c. According to Theorem 5 P\({}_{1}\)(4) is connected to P\({}_{2}\)(4). The possible SS values for these 2 vertices are, respectively: SS = 2,2,3,4, and SS = 2,3,3,4.