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$
0

1 Answer 1

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$
6
  • $\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, 2018 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$ Dec 31, 2018 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$ Dec 31, 2018 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, 2018 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$ Dec 31, 2018 at 15:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .