1.2.2 Number of edges

Remark 1.2.6   We can construct any graph together with its incidence matrix from scratch, adding edge by edge. That is, start with a graph with $\alpha$ vertices $A_1,\dots,A_{\alpha}$ and no edges at all. Note that the incidence matrix of this graph is the $\alpha\times\alpha$ matrix filled with zeros.

Now adding an edge we should distinguish between the loops and the edges connecting different vertices. Adding a loop to the vertex $A_i$ we have to replace $m_{ii}$ by $m_{ii}+1$ . Adding an edge that connects $A_i$ with $A_j$ , where $i\ne j$ , we have to replace both $m_{ij}$ and $m_{ji}$ by $m_{ij}+1$ and $m_{ji}+1$ , correspondingly. Note that by induction it follows that $m_{ij}=m_{ji}$ for all $i,j$ .

These remark makes the following statement obvious:

Lemma 1.2.7   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. Then the total number of edges of this graph is

$$\sum_{1\le i\le j\le\alpha}m_{ij}.$$

Exercise 1.2.8   If you feel it necessary, construct the rigorous inductive proof of Lemma .

Exercise 1.2.9   List all the possible incidence matrices of connected graphs with 1,2 and 3 edges.

Control question 1.7   Give the number of matrices, you have got in Exercise .

Control question 1.8   Would Exercise  remain reasonable if we omit the word "connected"?

You may use the answer form at the end of this lecture to answer these questions.