< Back | Next | Content >

A Tale of Vertex-Degree

The number of edges supported by a vertex is called degree of vertex. Degree of vertex is very important to graph family because it represents how honorable they are. Degree of vertex is also called Valency .

An isolated vertex has zero degree. Graph that contains no edge is called Null graph because they have null degree of vertices.

One edge supported by two vertices. Each of these connected vertices has degree 1, the total degree of vertices in the graph bellow is 2

The graph below has two edges. The two edges are supported by three vertices. Each of these connected edges has degree 2, the total degree of vertices in the graph is 4

Some graph likes to have a loop because a loop will give two degree of vertex directly. Two edges, one form a loop to vertex a, and one is connecting vertex a to vertex b. Vertex a has degree 3 and vertex b has degree 1, the total degree of vertices of the graph below is 4.

deg a = 3, deg b = 1

Because each edge needs to be supported at two ends, the sum of all degree of vertices (=valency) in a Graph is equal to twice the number of edges. This conclusion is often called Handshaking lemma . When people in a meeting is represented by vertices, and shaking hand between two people represented by an edge, then the total number of hands shaken is equal to double the number of handshakes. Thus in any graph, the sum of all degrees of vertices is an even number (if 0 is considered as even number).

Now let us play hide and seek with Graphs. A graph name G is hiding, and calling you "I have 10 edges and each vertex has degree 4. Can you guess how many vertices do I have?"

Another graph name H also hiding and claims that it has 7 edges and each vertex has 3 degrees. Do you think graph H is telling the truth or not?