Introduction to Graph Theory · Problem 3.6

Multigraphs — Darij Grinberg

Mathematics — Graph Theory · incidence-matrix-rank

Problem

Let

F

be any field. (For instance,

F

can be

\mathbb{Q}

\mathbb{R}

\mathbb{C}

.) Let

G = (V, E, \varphi)

be a multigraph, where

V = \{1, 2, \ldots, n\}

for some

n \in \mathbb{N}

. For each edge

e \in E

, we construct a column vector

\chi_e \in F^n

(that is, a column vector with

n

entries) as follows: • If

e

is a loop, then we let

\chi_e

be the zero vector. • Otherwise, we let

u

and

v

be the two endpoints of

e

, and we let

\chi_e

be the column vector that has a

1

in its

u

-th position, a

-1

in its

v

-th position, and

0

s in all other positions. (This depends on which endpoint we call

u

and which endpoint we call

v

, but we just make some choice and stick with it. The result will be true no matter how we choose.) Let

M

be the

n \times |E|

-matrix over

F

whose columns are the column vectors

\chi_e

for all

e \in E

(we order them in some way; the exact order doesn't matter). Prove that

\operatorname{rank} M = |V| - \operatorname{conn} G,

where

\operatorname{conn} G

denotes the number of components of

G