1
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics. $\endgroup$ – BrunoBern Dec 31 '18 at 3:33
  • $\begingroup$ @BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before. $\endgroup$ – Zachary Hunter Dec 31 '18 at 3:37
  • $\begingroup$ A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement. $\endgroup$ – Zachary Hunter Dec 31 '18 at 3:40
  • $\begingroup$ Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2. $\endgroup$ – BrunoBern Dec 31 '18 at 15:06
  • $\begingroup$ Manipulating Euler's formula, you can get the conclusion that $E \leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E \leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic. $\endgroup$ – Zachary Hunter Dec 31 '18 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.