1.2.3 Valencies

Definition 1.2.10   The total number of edges incident to a given vertex, where loops are counted twice, is called the valency of the vertex.

Lemma 1.2.11   Let a matrix

$$\left ( \begin{array}{ccc} m_{11}&\d... ...\dots&\dots&\dots\\ m_{\alpha1}&\dots&m_{\alpha\alpha}\\ \end{array}\right )$$

be an incidence matrix of some graph with the vertices $A_1,\dots,A_{\alpha}$ . Then for any $i$ , $i=1,\ldots,\alpha$ , the valency of $A_i$ equals

$$m_{ii}+\sum_{j=1}^{\alpha}m_{ij}.$$

Control question 1.9   Provide a proof of Lemma .

You may answer this question using answer form at the end of this lecture.

Exercise 1.2.12   Classify all the possible connected graphs with valencies of all the vertices not exceeding 2.

Exercise 1.2.13   List all the possible connected graphs with 1,2, 3,4 and 5 edges and with valencies of all the vertices not exceeding 3.

Project A. 1 (Low edge graphs)   Please, list all connected graphs with 1,2,3,4 edges.