Discrete Mathematical Structures by Pearson

Topics in Graph Theory 10-23

10.8.2 Incidence Matrix

Let G be a graph with n vertices and m edges. The incidence matrix M = [m

ij

] of order n × m is

defined by

m

ij

= 1 if vertex V

i

is incident on edge e

j

= 0 otherwise

The matrix has a row for every vertex and a column for every edge.

Consider the graph shown in Fig. 10.28 consisting of 5 vertices and 7 edges which can be

represented by the incidence matrix of order 5 × 7, that is,

v

2

v

3

e

3

e

2

e

5

e

6

e

7

e

4

e

1

v

5

v

4

v

1

Figure 10.28

eeeeeee

M

v

v

v

v

v

1 234567

1

2

3

4

5

1001000

1110000

0100110

0011101

0000

=

0

011

































(incidence matrix)

Some Important Results for Incidence Matrix

1. Each column contains exactly two unit ...