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.

Tagged with: , , ,

Leave a Reply