对于一种特殊类型的问题，我们也将采用一种特殊的方法——“交错标记法”来判断它是否有哈密顿通路或回路。先举个例子来说明这种方法的应用。
判断图90(a)是否具有哈密顿通路。
我们给图90上的某一个顶点，例如最上面的一个顶点标记上A，然后给和它相邻的各顶点标上B，接着再给和标记着B的顶点相邻的各顶点标记上A，……依次类推，直到图上所有的顶点都标记上A或B为止，如图90(b)所示。
由于图90(b)上的16个顶点交错标记了A和B，所以，如果图90上存在一条哈密顿通路的话，它必然要交错地走过顶点A和顶点B。也就是说：如果走到了A点的话，下一步无论沿着哪条边走，也只能走到B点；如果从B点出发，无论怎样走，也只能走到A点。这样，在这条哈密顿通路上，只能交错地出现顶点A，B，A，B，……而不可能连续地出现两个A，例如：A，B，A，A，B，……或者出现两个连续的B。然而，在39(b)上，标记是A的顶点共有9个，标记是B的顶点共有7个，这样，A就比B多了2个。要想把这16个顶点一次都走到，并且不重复，无论怎样安排这些顶点的顺序，总是至少要有2个A点挨在一块儿才行。也就是说，如果图90(b)有一条哈密顿通路的话，它必须要连续地经过2个A点才行。但是，根据我们对图90(b)进行的标记，在图90上的任何一条通路是不可能连续地经过2个A点的，于是可以看出在90(b)上是不可能存在哈密顿通路的，这样，原来的图90(a)自然也就不存在哈密顿通路了。
下面我们再来看看前面提出的棋盘上跳马问题：
马能否在半个棋盘上连续地把每个方格都跳到一遍？
我们可以考虑这样一个图：让它的顶点对应棋盘的方格，如果马从棋盘上的一个格能跳到另一个格，就在这两个格对应的顶点间连上一条边。这样，原来的问题就可以转变成判断棋盘所对应的这个图是否有一条哈密顿通路的问题了。
在这里，顶点的邻接方式是由跳马的方式决定的，也就是说每个顶点只能跟和它组成一个“日”字的对角线上的顶点邻接。棋盘上组成“日”字对角线的方格所着的颜色正好是相反的，我们让图上每个顶点着上它所对应的方格的颜色，这样，图上每条边所关联的两个顶点的颜色都是一黑一白，于是图上所有的顶点正好是黑白交错标记的。在这个图上，如果有一条哈密顿通路的话，棋盘上的顶点也必然是黑白交错出现的。
在半个棋盘格上，黑、白方格的格数是相同的，这就是说它们对应的黑、白顶点的个数也是相同的，这就不排除存在哈密顿通路的可能性。我们仍采取试探的方法来找这条通路。在这里我们不准备详细画出半个棋盘所对应的那个图，只给出一个具体的答案，见图91。图91中右上角的黑方格是通路的起点。
现在再来回答这个问题的第二部分：如果把半个棋盘对角线上的两个黑色方格去掉，那么，是否还存在一条同样性质的通路呢？我们仍然采用“交错标记法”，把它转换成求对应的图是否存在哈密顿通路的问题。不过，这里为了叙述上的方便，我们直接对棋盘进行分析。这时，由于去掉了两个黑色的方格，剩下的棋盘里白色方格要比黑色方格多2个，如图92。在这种情况下，要想仍然以马跳日的方式把每个方格都跳到一次并且仅仅一次，
就得连续地在2个白格之间跳一次才行。然而，根据棋盘的构造——任何一个日字的对角线上两个方格颜色都是相异的，因此，这一步跳是无法实现。这样，对于去掉两个黑色方格的半个棋盘来说，马是无法连续地把每个方格都跳到一次并且仅仅一次的。
采用交错标记法，判断以上这类问题的哈密顿通路是否存在，是比较简便的。但是，并非所有判断一个给图93定的图的哈密顿通路的问题都能采用这种方法。只有在对顶点进行交错标记而不会发生矛盾的时候，也就是图的同一个顶点不会同时被标上不同记号的时候，才可以使用。对于有些图，例如图93，就不能进行交错标记，因此也就不能采用这种方法判断它是否具有哈密顿通路。
另外一点需要注意的是，交错标记法一般用在否定一个图具有哈密顿通路的情况。把一个图的顶点交错标记了两种符号之后，如果其中一种符号的个数比另一种多2个以上，例如图90(b)和图91，那么，这种图一定不存在哈密顿通路。但是，如果一个图的顶点交错标记的两种符号的个数正好相等，或者只相差1个，这时，我们不能仅仅根据这一点就肯定图上一定存在哈密顿通路，而只能说有存在的可能性，不能说有存在的必然性。例如，对于图91，这种可能性由于确实找到了一条哈密顿通路而变成了现实。对于图94，虽然把它的顶点交错标上黑色和白色后，黑色顶点和白色顶点的个数相等，都是5个，但是这个图并不存在一条哈密顿通路。因此对于具体的图，判断它是否具有哈密顿通路，一定要作具体的分析才行。
