Harris Graphs: Tough Eulerian Graphs that are not Hamiltonian

  • Eulerian graph: a connected graph where all vertices have an even degree.

  • Tough graph: A graph G is tough if, for every subset S of the vertices of G, the number of components of G \ S is at most the number of vertices in S (more info here).

  • Hamiltonian cycle: a path that ends at the vertex it started and visits all vertices exactly once (The first vertex is technically visited twice - once in the beginning and once at the end).

Feel free to play around with the graphs below to test the G \ S condition. To delete a vertex, right click on it and hit delete. If you find a new Harris Graph or believe that one of the graphs listed here isn't a Harris graph, fill out the Prospective Harris Graph or Error Reporting Form respectively.

Doug Shaw-9-14

Discovered in 2013.

Jayna Fishman-Elizabeth Petrie-9-15

Discovered in 2013.

Jayna Fishman-Elizabeth Petrie-12-20

Discovered in 2013.

Jungmin Kwon-Jingheng (Sunny) Li-Minseo Son-Ruihan Wang-15-27

Discovered in 2016.

Alex Leaf-9-15

Discovered in 2016. Simplified version of ZackJoseph-12-18.

Doug Shaw-18-30

Discovered in 2016.

Hirotaka-7-12

Discovered in 2018. Minimal Harris graph.

2019Students-8-14

Discovered in 2019.

Zach DeVivo-Marco Troper-10-18

Discovered in 2022.

Shubhra Mishra-11-20

Discovered in 2022.

Zhennong Li-13-23

Discovered in 2022.

Jacob-15-25

Discovered in 2022.

Harris Graph Checker (created by Hirotaka Yoneda)