In an undirected graph, if there are more than 1 undirected edges associated with a pair of vertices, these edges are called parallel edges, and the number of parallel edges is called multiplicity. In a directed graph, if there are more than 1 directed edges associated with a pair of vertices, and the start and end points of these edges are the same (that is, their directions are the same), these edges are called parallel edges. A graph with parallel edges is called a multigraph, and a graph without parallel edges and cycles is called a simple graph.

(directed graph handshake theorem) Let d =

D(vi)=2m，D+(VI) = D-(VI) = m。

It is inferred that the number of odd vertices in any graph (undirected or directed) is even.

Let g =

For an undirected graph with vertex calibration, its degree sequence is unique.

For a given non-negative integer sequence d = (d 1, d2, ..., dn), if there is an undirected graph of order n g, v = {v6 5438+0, v2, ..., vn} as a vertex set, so that d(vi)=di, then d is said to be graphable.

In particular, if the obtained graph is a simple graph, D is said to be simply graphable.

Theorem 14.3 Let non-negative integer sequence d=(d 1, d2, …, dn), then d can be graph if and only if di=0(mod2).

Proof: ellipsis

Theorem 14.4 Let G be an arbitrary undirected simple graph of order n, then δ (G) ≤ n- 1.

Example 14.2 Determine which of the following non-negative integers are graphable? What can be simply represented by a chart?

( 1)(5,5,4,4,2, 1) (2) (5,4,3,2,2) (3) (3,3,3, 1)

(4) (d 1，d2，…，dn)，d 1 & gt； D2>…, dn>= 1, and di is an even number.

(5) (4,4,3,3,2,2)

Solution: Everything except (1) can be drawn, and only (5) can be drawn simply.