2
$\begingroup$

I proved that if $ G$ is a self-dual polyhedral graph that is also self-complementary then we have that the order (number of vertices) is $8$ and the size (number of edges) is $14$. Moreover, I proved that the degree sequence of $G$ has the following form $4,4,4,4,3,3,3,3$. But actually, I'm struggling from this to draw an explicit example, I cannot find any, the main problem is that any graph that I draw with this degree sequence is non-self-dual. Hence my questions: There exists such graph? How to prove existence? How to find an explicit example?

$\endgroup$
1
  • $\begingroup$ Is a quadrilateral prism with one diagonal at each base good enough? $\endgroup$
    – kabenyuk
    Feb 1, 2022 at 4:27

1 Answer 1

3
$\begingroup$

There are altogether $10$ self-complementary graphs with $8$ vertices, so it is not too terrible to check them by hand. You can find a list in .g6 format here.

Only the following four have the degree sequence you want:

enter image description here

Graph 1 (numbered from left to right) is not self-dual: the vertices of degree $3$ come in two adjacent pairs, but none of the faces of length $3$ share an edge.

Graphs 2, 3, and 4 are self-dual. I think it's easier to check this for graph 2, because it's highly symmetric. The vertices of degree $3$ come in two adjacent pairs, the faces of length $3$ come in two adjacent pairs, and any way of matching those up can be completed to an isomorphism between the graph and its dual.

All three are planar, but if your definition of polyhedral is "planar and $3$-connected", then that excludes graph 2: it is only $2$-connected.

$\endgroup$

You must log in to answer this question.

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