We got experimental evidence against the semi strong perfect graph theorem
and would like to learn what is wrong with it.


From [Recognizing the P4-structure of bipartite graph](https://reader.elsevier.com/reader/sd/pii/S0166218X99001043?token=95BAE4CC0839E24CC218B933184ED467786AF8799730EAA190CC2E2E1412A9F12C57EA719ED0FA8FD2E4ABC2A7973546&originRegion=eu-west-1&originCreation=20211225051901)



> 
> The P4-structure of a graph $G=(V; E)$ is a hypergraph $H=(V;E)$ such that the hyperedges from $H$ correspond to the vertex sets of the induced P4s in $G$.
> The **semi strong perfect graph theorem** states that a graph is perfect if and only if it has the P4-structure of a perfect graph.
> 
> 
> 


Evidence against this.
Let $G$ be the perfect graph:



```
G=Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 6), (2, 9), (3, 4), (3, 5), (4, 5), (4, 7), (5, 10), (6, 7), (6, 8), (7, 8), (8, 11), (9, 10), (9, 11), (10, 11)])

```

Let H be the P4-structure of G with 492 edges given [here](https://pastebin.com/raw/i3NWGFhZ).


$H$ is not perfect according to Sagemath.



> 
> Q1 What is wrong with this counterexample?
> 
> 
> 


Code can be tested on [Sagemath online](https://sagecell.sagemath.org/).



What is wrong with the experimental evidence against the semi strong perfect graph theorem?
This is not a counterexample. $H$ is the $P\_4$-structure of $G$, a certain 4-uniform hypergraph, and $G$ is perfect. All you can derive from the theorem is that any graph with the same $P\_4$-structure $H$ must be perfect.


Besides, $H$ is a hypergraph. While one may try to somehow create a graph out of it, and check whether it's perfect, it has no relation to the theorem in question.


