Dual Graph Score

105 Views Asked by At

Continuous graph G with the following score(degrees of it's vertices) (4, 4, 4, 4, 4, 4, 5, 5), has some planar embedding in which every face is bound by a graph cycle.

Determine the number of faces of G and their degrees. (In other words what is the score of the dual graph of G?)

Using Euler's formula to calculate the number of faces: $f = 17 - 8 + 2 = 11 $

1

There are 1 best solutions below

1
On BEST ANSWER

To get the degree of a vertex in the dual graph, we just need to know how many edges bound the corresponding face in the original graph. You have seen that there are $17$ edges and $11$ faces in $G.$ Since each edge belongs to two faces, if we count the edges face-by-face we get $34.$

Each face has at least three edges bounding it, for if we had a face bounded by only one or two edges, $G$ would not be a simple graph. (The question does not say that $G$ is simple, but since I see no way to do the problem otherwise, I'm assuming that "graph" means "simple graph.") So, we need $11$ integers, each $\ge 3$ whose sum is $34.$

The score can only be $(3,3,3,3,3,3,3,3,3,3,4)$