Find amount of vertice of grade 3 or 4 in planar graph

53 Views Asked by At
A planar, loop free connected graph has
8 vertices of either degree 3 or 4
7 faces
How many of the vertices are either degree 3 or 4

Since its a planar graph I assume we use |V | − |E| + #(faces) = 2 and we change the formula to E = V + F - 2 and we get 13 edges. I'm not sure how to go from there .

1

There are 1 best solutions below

2
On BEST ANSWER

We know Euler's formula for a connected planar simple graph $G=(V,E)$ with $e=|E|$ and $v=|V|$: $$ v+f=e+2,\tag{1} $$

From $(1)$ we will get that your graph has $13$ edges.

Also we know the next formula (the "First Theorem of Graph Theory" or the "Handshaking Lemma"): $$ \sum_{{v}\in{V}}\text{$deg(v)$}=2e,\tag{2} $$

From $(2)$ we will have that $$ \begin{cases} v_1+v_2=8,\\ 3v_1+4v_2=26.\tag{3} \end{cases} $$

Here $v_1$ is the quantity of vertices having the degree is equal to $3$ and $v_2$ is the quantity of vertices having the degree is equal to $4$. From $(3)$ we will obtain that your graph consists of $2$ vertices having $4$ degrees and $6$ vertices having $3$ degrees.