Grinberg-Introduction-Graph-Theory · Problem 3.8

Multigraphs

Mathematics — Graph Theory · multigraph-friendly-couple-decomposition

Problem

Let

G = (V, E, \varphi)

be a connected multigraph with

2m

edges, where

m \in \mathbb{N}

. A set

\{e, f\}

of two distinct edges will be called a friendly couple if

e

and

f

have at least one endpoint in common. Prove that the edge set of

G

can be decomposed into

m

disjoint friendly couples (i.e., there exist

m

disjoint friendly couples

\{e_1, f_1\}, \{e_2, f_2\}, \ldots, \{e_m, f_m\}

such that

E = \{e_1, f_1, e_2, f_2, \ldots, e_m, f_m\}

). (``Disjoint'' means ``disjoint as sets'' -- i.e., having no edges in common.) [Hint: Induct on

|E|

. Pick a vertex

v

of degree

> 1

and consider the components of

G \setminus v