Theorem 3.4  (해밀턴 그래프가 되기 위한 필요 조건)

IF G = (V, E) 는 해밀턴이고  어떤 V의 적어도 한개를 포함하고 있는  재대로된 서브 집합이면, 그래프 G-W는 거의|W|를 가진다.

Proof. Gi (i=1,2, . . . . . , k) 는 G-W의 분명한 요소들이며, 그리고  C는 그래프 G안에 어떤 해밀턴 사이클이다. G이다. 만약 C안의 최근 정점이 that  Gi에 속하고 ui에 의해 조짐이 보여지며, 사이클 안에 그 정점 즉시 후히 ui, 각 i 에 W안에 필요하다.. 그래서 각 요소 정의들은 W안에 한 독특한 정점이다. 이러한 이유로,  분명한 요소들의 수는 W의 카디널리티를 초과 할 수 없다.

example 5

이론 3.4의 과목은 실패이다. 그 완전 이분 그래프 K2,n (where n>2) 절단 정점을 가지며, 그러나 이것은 헤밀턴은 아니다.

우리는  spanning cycles들의 존재에 몇가지 충분 조건을 얻을 것이고  쳅터의 끝 풀이 문제들 안에 임의의 그래프 안에 spanning paths. n개의 정점이 있는 간단한 그래프와 많은 애지가 가능한 완벽 그래프, 어떤 카디널리 헤밀턴.  다시말해서, 각 정점의 차수가 n-1이면, 그 그래프는 해밀턴이다.  대체가능한  이 필요한 더 약한 상황이고 연결된 그래프 안에 해밀턴 사이클의 증명을 아직 보장하는가? 이점에서 , 앞에서 언급한 충분 기준은 우아한 결과이다.

이론 3.5 (Ore's Theorem: A sufifcient condition for a graph to be Hamiltonian). n개의(where n>2) 정점들을 가진 간단한 그래프는 해밀턴 그래프이다. 만약 인접해있지 않은 정점들의 모든 pair의 차수들의 합이 최근에 n이다.

proof n개의 정점들을 가진 그래프 G를 가정하고 불평등조건을가진며 해밀턴이 아니다. 그래서 t소수의 edge와 함께 완전그래프 Kn의 서브그래프이다. 우리는 그래프에 edge들을 인접하지 않은 정점들을 재귀적으로  더한다. 아직 우리는 그래프 H  각각 that 더한다 하나 더 edge 연결하여 두 인접하지 않은 정점들 H안에 

이건 나중에하자 번역힘듬

이론3.6 n 정점들(where n>2)가진 심플 그래프는 해밀턴이면 모든 정점의 차수는 최근 n/2이다

pfoof.

Example 6 이론 3.5와 이론 3.6 둘다 다루어보자 실패이다. 5개에서 좀더 많은 정점들을 가진 순환 그래프는 해밀턴 그래프이며, 그러나  그래프안에 모든 정점 차수는 오직 2이다.  정점들의 모든 쌍의 차수의 합은 오직 4이다.

이론 3.7 n개의 정점들을 가진 그래프 G는 해밀턴 연결이다. 어느 두개의 인접하지 않은 정점들의 차수의 합이 n보다 더하다?. 특히, 이것이 해밀턴 연결이면 각 정점의 차수는 n/2보다 더하다?

http://itphotostory.tistory.com/53

http://www.mediawiki.org/wiki/Manual:Enable_TeX/ko#.EB.A6.AC.EB.88.85.EC.8A.A4.EC.97.90.EC.84.9C_.EC.84.A4.EC.B9.98.ED.95.98.EA.B8.B0

Hamiltonian graphs and digraphs

한 그래프 안에 두 정점들 사이에 한 path는 해밀턴 path 이면 이것은 그래프의 모든 정점들을 통하는 pass이다. 한 가까운 해밀턴 path는 그래프 안에  해밀턴 사이클이라고 불린다. 다시 말해서, 한 해밀턴 path는 spanning path이며, 또 해밀턴 cycle은 spanning cycle이다. 해밀턴 그래프는 해밀턴 사이클을 가진 그래프이다. 모든 해밀턴 그래프는 해밀턴 path 가지고 있으며, 그러나 정반대는 진실이 아니다; 그래프에 path를 고려해야된다. 해밀턴 그래프의 우리의 논의는, 우리는 간단한 그래프들 우리의 주의를 제한한다. 왜냐하면 즉시 정점을 통한 pass를 고려해야된다. 유도된 그래프들의 경우 안에, 정의들 유사하다.

오일러 그래프와 달리, 여긴 해밀턴 그래프들의 묘사는 우아하지 않으며(쉽게 검증가능), 많은 필요족건을 통하여 짝수이고 많은 충분 조건은 알려진 spanning cycles의 존재이고 연속된 그래프안에 spanning paths고 약한 연결 방항성그래프이다. 물론, 어떤 해밀턴 그래프는 필연적으로 2-연결된 이전 정점의 삭제로부터 그래프 결과들 연결된 그래프 안에 해밀턴 path를 가진다.(??)   그 결과, 그래프 아님과 함께 절단 정점 해밀턴이다. 모든 사이클 그래프는 해밀턴이며, 또한 모든 완전 그래프 이며 3개 또는 더 많은 정점들을 가진다. 연결된 상호 그래프 Km.n은 해밀턴이면 오직 m=n 성립한다.

따라서 필요한 조건은 fact의 간단한 일반화  그것은 해밀턴 그래프의  정점이 없는 절단 정점이다.