< 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.

Handshaking lemma Handshaking lemma

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

Handshaking lemma

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

Handshaking lemma

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.

Handshaking lemma

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?

Answers:

Using handshaking lemma we know that the sum of degree of vertices is twice the number of edges. Thus graph G with 10 edges has total 20 degrees of vertices. Each vertex has degree 4, thus graph G has 20/4 = 5 vertices.

Graph H tell us that it has 7 edges, which is equal to total of 14 degrees of vertices. Each vertex has degree 3, but 14/3 is not a whole number, thus Graph H is not telling the truth.


< Back | Next | Content >

Teknomo, Kardi (2015) Pictorial Introduction to Graph Theory. http:\\people.revoledu.com\kardi\tutorial\GraphTheory\