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?
Self-dual polyhedral and self-complementary graph
graph theorypolyhedra
Related Solutions
Let $\varphi$ be the isomorfism $\varphi: G\rightarrow \overline G$ and let $\theta$ be the isomorphism $\theta:H\rightarrow \overline H$.
Consider the function $\sigma: F\rightarrow \overline F: f(v)=\left\{ \begin{array}{ll} \varphi(v) & v\in G \\ \theta(v) & v\in H \end{array}\right .$
We have to show that $\sigma(uv)$ is not an edge of $F$ if and only if $uv$ is not an edge of $F$ ( this would prove $\sigma$ is an isomorphism).
We clearly only need to check the case $u\in G$ and $v\in H$.
Notice that $d(\theta(v))$=n-d(v)-1$ for all $v\in H$. So we have:
$uv\in F \iff d(v)<n/2\iff n/2<n-d(v)\iff n/2\leq n-d(v)-1=d(\theta(v))\iff \varphi(u)\theta(v)\not\in F\iff \sigma(uv)\not \in F$
For any $n\in\mathbb N,$ here's how you can construct a self-complementary graph of diameter $2$ and order $4n+1.$
Choose a graph $G$ of order $n.$
Start with a $C_5$ graph, with vertices $A,B,C,D,E$ and edges $AB,BC,CD,DE,EA.$
Replace each of the vertices $B$ and $E$ with a copy of $G,$ and replace each of the vertices $C$ and $D$ with a copy of the complementary graph $\overline G.$
More precisely: The graph has vertex set $A\cup B\cup C\cup D\cup E$ where $A,B,C,D,E$ are disjoint sets and $|A|=1$ and $|B|=|C|=|D|=|E|=n.$ The induced subgraphs on $B$ and $E$ are isomorphic to $G,$ the induced subgraphs on $C$ and $D$ are isomorphic to $\overline G.$ There are edges joining all vertices in $A$ to all vertices in $B,$ all vertices in $B$ to all vertices in $C,$ all vertices in $C$ to all vertices in $D,$ all vertices in $D$ to all vertices in $E,$ and all vertices in $E$ to all vertices in $A.$ On the other hand, there are no edges between $A$ and $C,$ or between $C$ and $E,$ or between $E$ and $B,$ or between $B$ and $D,$ or between $D$ and $A.$
In other words: Just use the most obvious construction of a self-complementary graph of order $4n+1.$
Example: For $G=K_2$ it looks like
Best Answer
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
.g6format here.Only the following four have the degree sequence you want:
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.