§10.
2 Graph Terminology
1. Introduction page 651
2. Basic Terminology
(1) Definition 1 (page 651)
Two vertices u and v in an undirected
graph G are called adjacent ( 相邻的， or
neighbors) in G if {u,v} is an edge of
G.
If e={u,v}, the edge e is called incident ( 关
联的 ) with the vertices u and v. The
edge e is also said to connect u and v.
The vertices are called endpoints of
the edge {u, v}.
(3) Definition 3 (page 652)
The degree of a vertex in an undirected
graph is the number of edges incident
with it, except that a loop at a vertex
contributes twice to the degree of the
vertex. The degree of the vertex v is
denoted by deg(v).
Example: Figure 1 (page 652)
For Graph G, deg(e)=3, deg(g)=0.
For Graph H, deg(e)=6, deg(b)=6
A vertex of degree zero is called
isolated. It follows that an isolated
vertex is not adjacent to any vertex.
A vertex is pending if and only if it has
degree one. Consequently, a pending
vertex is adjacent to exactly one other
vertex.
(4) The Handshaking Theorem
Let G=(V, E) be an undirected graph
with e edges. Then
2e = ∑v∈V deg(v)
(Note that this applies even if multiple
edges and loops are present.)
Example 3 (page 653): How many edges
are there in a graph with ten vertices
each of degree six?
Answer: e=30
(5) Theorem 2 (page 653)
An undirected graph has an even ( 偶数 )
number of vertices of odd ( 奇数 ) degree.
Proof:
V1---- the set of vertices of an even degree
V2---- the set of vertices of an odd degree
2e = ∑v∈V deg(v)
= ∑v∈V1 deg(v) + ∑v∈V2 deg(v)
(6) Definition 4 (page 654)
When (u, v) is an edge of the graph G
with directed edge, u is said to be
adjacent to v and v is said to be
adjacent from u.
The vertex u is called the initial
vertex of (u,v), and v is called the
terminal or end vertex of (u,v). The
initial vertex and terminal vertex of a
loop are the same.
(7) Definition 5 (page 654)
In a graph with directed edges the in-
degree of a vertex v ( 入度 ), denoted by
deg-(v), is the number of edges with v as
their terminal vertex.
The out-degree of v ( 出度 ), denoted by
deg+(v), is the number of edges with v as
their initial vertex .
Note: a loop at a vertex contributes 1 to
both the in-degree and the out-degree of
this vertex.
(7) Theorem 3 (page 654)
Let G=(V, E) be a graph with directed
edges. Then
∑v∈V deg-(v) =∑v∈V deg+(v) = |E|
3. Some Special Simple Graphs
(1) Example 5 (Complete Graph, 完全图
page 655)
The complete graph on n vertices,
denoted by Kn, is the simple graph that
contains exactly one edge between
each pair of distinct vertices.
(2) Example 6 (Cycles, page 655)
The cycle Cn, n≥3, consists of n
vertices v1, v2, …, vn and edges {v1, v2},
{v2, v3}, … , {vn-1, vn}, and {vn, v1}.
(3) Example 7 (Wheels, 轮 , page 655)
We obtain the wheel Wn when we add
an additional vertex to the cycle Cn, for
n≥3, and connect this new vertex of the
n vertices in Cn, by new edges.
(4) Example 8 (n-Cubes, page 655)
The n-dimensional cube, or n-cube,
denoted by Qn, is the graph that has
vertices representing the 2n bit strings of
length n.
Two vertices are adjacent if and only if
the bit strings that they represent differ
in exactly one bit position.
Question:
How to construct the (n+1)-cube Qn+1
from the n-cube Qn (page 655)?
Way:
By making two copies of Qn,
prefacing the labels on the vertices
with a 0 in one copy of Qn and with a 1
in the other copy of Qn, and adding
edges connecting two vertices that
have labels different only in the first bit,
4. Bipartite Graphs ( 二分图 )
(1) Definition 5 (page 656)
A simple graph G is called bipartite if
its vertex set V can be partitioned into
two disjoint sets V1 and V2 such that
every edge in the graph connects a
vertex in V1 and a vertex in V2.
Note: no edge in G connects either two
vertices in V1 or two vertices in V2.
(2) Example 9 (page 656)
C6 is bipartite, as shown in Figure 7
(page 656)
V1 = {v1, v3, v5}
V2 = {v2, v4, v6}
(3) Example 10 (page 656)
K3 is not a bipartite.
(4) Example 11 (page 656)
Are the graphs G and H displayed in
Figure 8 bipartite?
G:two disjoint sets {a, b, d} and {c, e, f, g}
H: not bipartite (consider a,b,f)
(5) Theorem 4 (page 657)
A simple graph is bipartite if and only if it
is possible to assign one of two colours
to each vertex of the graph so that no
two adjacent vertices are assigned to the
same colour.
Example 12: Use Theorem to determine
whether the graphs in Example 11 are
bipartite.
Another useful criterion for determining
whether a graph is bipartite is based on
the notion of a path. A graph is bipartite
if and only if it is not possible to start at a
vertex and return to this vertex by
traversing an odd number of distinct
edges.
(5) Example 13 (Complete Bipartite
Graphs, page 658)
The complete bipartite graph Km,n is
the graph that has its vertex set
partitioned into two subsets of m and n
vertices, respectively. There is an edge
between two vertices if and only if one
vertex is in the first subset and the
other vertex is in the second subset.
Bipartite graphs can be used to model
many types of applications that involve
matching the elements of one set to
elements of another.
5. New Graphs from Old
(1) Definition 7 (page 663)
A subgraph ( 子图 ) of a graph G=(V, E) is a
graph H=(W, F) where W⊆V and F⊆ E.
A subgraph H of G is a proper subgraph
( 真子图 ) of G if H ≠ G.
(2) Definition 9 (page 664)
The union of two simple graphs
G1=(V1, E1) and G2=(V2, E2) is the simple
graph with vertex set V1∪V2 and edge
set E1∪E2.
The union of G1 and G2 is denoted by
G 1∪ G 2.
(3) Example 19 (page 664)
Find the union of the graphs G1 and
G2