1. 基本术语
首先给出描述无向图的顶点和边的一些术语
1.1 邻接（相邻）
若u和v是无向图G中的一条边 e 的端点，则称两个顶点u和v在G里邻接（或相邻）。
这样的边e称为关联顶点u和v，也可以说边e 连接 u 和 v。
1.2 邻居
图G =（V，E）中，顶点v 的所有相邻顶点的集合称为顶点v的邻居，记作N(v)。
若A是V的子集，我们用N(A)表示图G中至少和A中一个顶点相邻的所有顶点的集合。所以N(A)=∪N(v)，v∈𝐴
1.3 顶点的度
在无向图中，顶点的度是与该顶点相关联的边的数目。顶点上的环为顶点的度做出双倍贡献，也就是说一个顶点增加一个环，度增加2。
顶点v 的度记成deg(v)
1.4 孤立点
把度为0的顶点称为孤立点。
因此孤立点不与任何顶点相邻。
1.5 悬挂点
顶点是悬挂点，当且仅当它的度是1。
因此悬挂点恰与1个其他顶点相邻。
例题
如图1所示，图G和图H的顶点的度、顶点的邻居是什么? 哪些点是孤立点，哪些点是悬挂点？
🔴解：
图G：
deg(a)=2，deg( b )=deg( c ) =deg( f )=4，deg( d )=1，deg( e )=3，deg( g )=0
这些顶点的邻居是N( a )={b，f}，N ( b )={a，c，e，f)，N( c )={b，d，e，f)，N( d )={ c }，N( e )={b，c，f)，N( f )={a，b，c，e} 和N( g )= ∅
图G的顶点g是孤立点，顶点d是悬挂点
图H：
deg( a )=4，deg( b )=deg( e )=6，deg( c )=1，deg( d )=5。
这些顶点的邻居是N( a )={b，d，e}，N( b )={a，b，c，d，e}，N( c )={b}，N( d )={a，b，e}和N( e )={a，b，d}。
图H的顶点c是悬挂点，没有孤立点
2. 握手定理
例题：
一个具有10个顶点且每个顶点的度都为6的图，有多少条边？
🔴解：
因为顶点的度之和是6·10=60，所以2m=60，其中m是边的条数。因此m=30
3. 握手定理的推论
定理：无向图有偶数个度为奇数的顶点。（ 偶数包含0 ）
4. 带有有向边的图的术语
带有有向边的图的术语反映出有向图中的边是有方向性的
4.1 邻接
定义：当(u,v)是带有有向边的图G的边时，我们称u邻接到v，而且说v从u邻接。
顶点u称为 (u, v) 的起点，v称为 (u, v) 的终点。
注意，环的起点和终点是相同的。
4.2 度——出度 和 入度
因为带有有向边的图 的边是有序对，所以这时顶点度的定义细化成把这个顶点作为起点和作为终点的不同的边数。
入度定义：在带有有向边的图里，顶点v的入度，记作deg-(v)，是以v作为终点的边数。
出度定义：顶点v的出度，记作deg+(v)，是以v作为起点的边数
注意，顶点上的环对这个顶点的入度和出度的贡献都是1。
4.3 例题：
例4：求出图2所示带有向边的图G中每个顶点的入度和出度
🔴解：
在图G中，
入度是：deg-(a) = 2， deg-(b) = 2，deg-( c) = 3，deg- (d) = 2，deg-(e) = 3，deg-(f) = 0。
出度是：deg+(a) = 4，deg+ (b)=1，deg+( c) = 2，deg+ (d) = 2，deg+(e) = 3，deg+ (f) = 0。
因为每条边都有一个起点和一个终点，所以在带有向边的图中，所有顶点的入度之和与所有顶点的出度之和相同。这两个和都等于图中的边数。把这个结果表述成下面的定理。
