2-2-2. Diamond Figure

Diamond figure is such a special figure class that embedding the figure in a graph inevitably makes the graph non-hamiltonian. Although hamiltonian passage and diamond figure has appeared on previous section, we give them strict definitions here.

Def.2-2-2.1: hamiltonian passage

Let a distinct paths set P, passing all points of not necessarily connected graph G, including 0 length paths, in other words points. When a proper points set S of G consists of all of the terminal points of P, we say "S has a hamiltonian passage P of G".

Def.2-2-2.2: diamond figure

When a proper points set S of not necessarily connected graph D has not a hamiltonian passage, we say "graph D is a diamond figure with conjunction part S".

When a proper subgraph D of connected graph G is a diamond figure and D connects with G only by the conjunction part S, (removing points of S divides graph G into D and the other part), we say "diamond figure D is embedded in graph G".

A hamiltonian passage is a spanning paths set of graph G and a diamond figure is such a graph that a points subset S of G has not a hamiltonian passage. Especially arbitrary even cycle is a diamond figure with conjunction part taking points on the cycle at intervals of one.

Theorem 2-2-2.1. embedding of diamond figure

When a proper subgraph Gd of graph G is a diamond figure and Gd is embedded in G, graph G is a non-hamiltonian graph.

Proof: Obvious by the definition of diamond figure.

Theorem 2-2-2.2. complete subgraph of non-hamiltonian graph

When non-hamiltonian graph G has a complete subgraph K, graph G is a diamond figure with conjunction part K. Especially, let two adjacent points of G x and y, graph G is a diamond figure with conjunction part {x, y}.

Proof: Obvious by the definition of diamond figure.

Can it be said that a diamond figure is embedded in every non-hamiltonian graph (as its proper subset)? The answer is probable to be negative. For example, such a graph as mesh graph is considered to be impossible to show some special part of the graph as diamond figure. Perhaps we can assume that non-hamiltonian graphs are separated into a class which has a diamond figure inside and another class which does not.

Any effective method to detect a diamond figure embedded inside of a graph is not developed so far. The difficulty of this problem is supposed to be equivalent that the complexity of k-terminal division experiment comes to exponential order in the worst case.