Harris graph

<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a Harris <a href="/facts/Graph_theory/VVPCd4TX">graph</a> is defined as an <a href="/facts/Eulerian_path/4l2G67c7">Eulerian</a>, <a href="/facts/Graph_toughness/92anGVk5">tough</a>, non-<a href="/facts/Hamiltonian_graph/MHjY2xoY">Hamiltonian graph</a>. Harris graphs were introduced in 2013 when, at the <a href="/facts/University_of_Michigan/6e1Ea5xh">University of Michigan</a>, Harris Spungen <a href="/facts/Conjecture/oPWUb7SF">conjectured</a> that any graph which is both <a href="/facts/Eulerian_path/4l2G67c7">tough</a> and Eulerian is <a href="/facts/Sufficient/G45aDCY9">sufficiently</a> Hamiltonian. However, Douglas Shaw disproved this <a href="/facts/Conjecture/oPWUb7SF">conjecture</a>, discovering a <a href="/facts/Counterexample/dnThYpHW">counterexample</a> with <a href="/facts/Order_of_a_graph/kw3eIBUe">order</a> 9 and <a href="/facts/Size_(graph_theory)/kw3eIBUe">size</a> 14. Currently, there are 241,375 known Harris graphs. The minimal Harris graph, the Hirotaka graph, has order 7 and size 12.
</p><p>Harris <a href="/facts/Graph_theory/VVPCd4TX">graphs</a> can be constructed by adding barnacles or grafting smaller Harris <a href="/facts/Graph_theory/VVPCd4TX">graphs</a>, enabling larger graphs while preserving their properties. Notable types include the minimal Hirotaka <a href="/facts/Graph_theory/VVPCd4TX">graph</a>, the barnacle-free Lopez <a href="/facts/Graph_theory/VVPCd4TX">graph</a>, and the Shaw <a href="/facts/Graph_theory/VVPCd4TX">graph</a>, each showcasing unique structural features in <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>. Harris graphs are valuable for teaching <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a> due to their accessible methods for finding and verifying them. They offer a balanced challenge, fostering creativity, teamwork, and problem-solving as students collaborate to explore solutions.
</p>

Harris graph open-in-new

Harris graph