I'm doing university exercises about planar graphs and they gave me the following:
Let G be a connected, self-complementary planar graph of order n and size
m having four vertices of degree two and the remaining vertices of degree d. If six faces of G are triangles and the remaining faces are pentagons, compute the values of d, n and m.
I'm not sure How Can I figure out the solicited values? I tried reach an equalization using the Euler form, the successions degree form and the sizes form for a complementary graph, but I had not success.
Has someone any idea ?
Thanks a lot!
Best Answer
Since G is self-complementary, it has half the number of edges as a complete graph of the same order.
$$m = \frac{n(n-1)}{4} = 4+(n-4)\frac{d}{2}$$
$$ n^2-n = 16+2nd-8d $$
Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)
Check for $d=5$:
$$ n^2-n = 16+10n-40 $$ $$ n^2-11n+24=0 \implies n=\{3,8\}$$
In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.
I will leave it to you to find the graph. Hint: add to the tetrahedron.