Study on necessary and sufficient conditions for Euler graph and Hamilton graph

摘要

Three theorems are proposed in this paper. The first theorem is that a connected undirected graph G is an Euler graph if and only if G can be expressed as the union of two circles without overlapped sides. Namely, equation E(c_1~E) + E(c_2~E) = E(G) satisfies. The second theorem is that a connected simple undirected graph G(V, E), (E>V) is a Hamilton graph if and only if G contains a sub-graph generated by union of circles of sub-graphs derived from two endpoints of common side. Namely, the equation V(c_1~H)+V(c_2~H)-V(G) = 2 satisfies (meaning of symbols in the equations see main body of this paper). The third theorem is that a connected simple undirected graph is a Hamilton graph if and only if the loop sum of two circles, c_1~H and c_2~H , of sub-graphs derived from two endpoints of common side in graph G is a sub-graphs of loop graph C_n.