## Abstract

A graph is intrinsically knotted if every embedding contains a nontrivially knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that there are exactly 14 intrinsically knotted graphs with 21 edges, in which the Heawood graph is the only bipartite graph. The authors showed that there are exactly two graphs with at most 22 edges that are minor minimal bipartite intrinsically knotted: the Heawood graph and Cousin 110 of the E_{9}+e family. In this paper we show that there are exactly six bipartite intrinsically knotted graphs with 23 edges so that every vertex has degree 3 or more. Four among them contain the Heawood graph and the other two contain Cousin 110 of the E_{9}+e family. Consequently, there is no minor minimal intrinsically knotted graph with 23 edges that is bipartite.

Original language | English |
---|---|

Article number | 113022 |

Journal | Discrete Mathematics |

Volume | 345 |

Issue number | 11 |

DOIs | |

Publication status | Published - 2022 Nov |

### Bibliographical note

Funding Information:The first author was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government Ministry of Science and ICT (NRF-2018R1C1B6006692).The third author was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. NRF-2017R1A2B2007216).

Publisher Copyright:

© 2022 The Authors

## Keywords

- Graph embedding
- Intrinsically knotted

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics