On page 556 (Grimaldi) is the following question:<\/p>\n
Let G be a loop-free connected undirected 3-regular graph (every vertex has degree 3), such that<\/p>\n |E| = 2|V| – 6<\/p>\n Find |V| and |E|.<\/strong><\/p>\n Solution:<\/p>\n First, |V|= number of vertices; |E| = number of edges. The degree of a vertex means how many edges are incident with it.<\/p>\n We know, for any undirected graph, the sum of the degrees of the vertices is equal to twice |E|:<\/p>\n Σ(deg) = 2|E|<\/p>\n In our case, the graph is 3-regular, so Σ(deg) = 3|V|. Then<\/p>\n 3|V| = 2|E|<\/p>\n which leads to <\/p>\n 3|V|\/2 = |E|<\/p>\n Given originally in the question,<\/p>\n |E| = 2|V| – 6<\/p>\n which means<\/p>\n 3|V|\/2 = 2|V| – 6<\/p>\n Multipltying by 2 on both sides gives<\/p>\n 3|V| = 4|V| – 12<\/p>\n Now, subtracting 4|V| from both sides yields<\/p>\n -|V| = -12<\/p>\n Finally, multiplying both sides by -1,<\/p>\n |V| = 12<\/p>\n Then<\/p>\n |E| = 2|V| – 6 = 2(12) -6 = 18<\/p>\n So, the graph has 12 vertices and 18 edges.<\/p>\n HTH:)<\/p>\n Source:<\/p>\n Grimaldi, Ralph P. Discrete and Combinatorial Mathematics<\/u>. Don Mills: Addison-
Wesley, 1994.<\/p>\n