Math: graph theory: a textbook example
The tutor offers a solution to a textbook graph theory question.
On page 556 (Grimaldi) is the following question:
Let G be a loop-free connected undirected 3-regular graph (every vertex has degree 3), such that
|E| = 2|V| – 6
Find |V| and |E|.
Solution:
First, |V|= number of vertices; |E| = number of edges. The degree of a vertex means how many edges are incident with it.
We know, for any undirected graph, the sum of the degrees of the vertices is equal to twice |E|:
Σ(deg) = 2|E|
In our case, the graph is 3-regular, so Σ(deg) = 3|V|. Then
3|V| = 2|E|
which leads to
3|V|/2 = |E|
Given originally in the question,
|E| = 2|V| – 6
which means
3|V|/2 = 2|V| – 6
Multipltying by 2 on both sides gives
3|V| = 4|V| – 12
Now, subtracting 4|V| from both sides yields
-|V| = -12
Finally, multiplying both sides by -1,
|V| = 12
Then
|E| = 2|V| – 6 = 2(12) -6 = 18
So, the graph has 12 vertices and 18 edges.
HTH:)
Source:
Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. Don Mills: Addison-
Wesley, 1994.
Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.
Leave a Reply
You must be logged in to post a comment.