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.
