IMO 1991 · Problem 4
Suppose \(G\) is a connected graph with \(k\) edges. Prove that it is possible to label the edges \(1,2,\ldots,k\) in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to \(1\).
[A graph consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices \(u,v\) belongs to at most one edge. The graph \(G\) is connected if for each pair of distinct vertices \(x,y\) there is some sequence of vertices \(x=v_0,v_1,v_2,\ldots,v_m=y\) such that each pair \(v_i,v_{i+1}\) \((0\leq i<m)\) is joined by an edge of \(G\).]
Official text of the problem. Official problem paper (PDF)
Solution
If \(k=0\), there is nothing to prove. Assume \(k\geq1\).
We construct a labeling by walking along unlabelled edges, with occasional changes of starting point. Choose a vertex \(s\) incident with an edge, begin at \(s\), and declare \(s\) visited. Apply the following rules:
- If the current vertex has an unlabelled incident edge, traverse any such edge, give it the next label \(1,2,\ldots,k\), and declare the vertex reached visited.
- If the current vertex has no unlabelled incident edge but unlabelled edges remain elsewhere, resume the walk from a visited vertex having an unlabelled incident edge.
We first justify that the second rule is always possible when needed. Let \(W\) be the set of visited vertices. Every labelled edge has both endpoints in \(W\). If no vertex in \(W\) had an unlabelled incident edge, there could be no edge between \(W\) and its complement: any such edge would necessarily be unlabelled. Since \(W\) is nonempty and \(G\) is connected, this would imply that every vertex belongs to \(W\), and consequently that no unlabelled edges remain—a contradiction.
Thus the construction continues until all \(k\) edges have received distinct labels \(1,2,\ldots,k\).
Now let \(v\) be any vertex belonging to at least two edges.
If \(v=s\), an edge incident with \(v\) has label \(1\), so the required greatest common divisor is \(1\).
If \(v\neq s\), consider its first visit. Since changes of starting point are allowed only to visited vertices, this first visit occurs by traversing an edge, say with label \(m\). Before this traversal, no edge incident with \(v\) was labelled, because both endpoints of every labelled edge have already been visited. As \(v\) has at least two incident edges, it therefore still has an unlabelled incident edge upon arrival. The first rule immediately traverses such an edge and labels it \(m+1\).
Hence two edges incident with \(v\) have consecutive labels. The greatest common divisor of all labels at \(v\) divides \[ \gcd(m,m+1)=1, \] so it equals \(1\), as required. \(\square\)
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1991 · Aufgabe 4
Es sei \(G\) ein zusammenhängender Graph mit \(k\) Kanten. Man beweise, dass man die Kanten so mit \(1,2,\ldots,k\) beschriften kann, dass an jedem Knoten, der zu mindestens zwei Kanten gehört, der größte gemeinsame Teiler der Zahlen, mit denen diese Kanten beschriftet sind, gleich \(1\) ist.
[Ein Graph besteht aus einer Menge von Punkten, die Knoten genannt werden, zusammen mit einer Menge von Kanten, die bestimmte Paare verschiedener Knoten verbinden. Jedes Knotenpaar \(u,v\) gehört zu höchstens einer Kante. Der Graph \(G\) heißt zusammenhängend, wenn es für jedes Paar verschiedener Knoten \(x,y\) eine Knotenfolge \(x=v_0,v_1,v_2,\ldots,v_m=y\) gibt, sodass jedes Paar \(v_i,v_{i+1}\) \((0\leq i<m)\) durch eine Kante von \(G\) verbunden ist.]
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Für \(k=0\) ist nichts zu beweisen. Wir nehmen \(k\geq1\) an.
Wir konstruieren eine Beschriftung, indem wir unbeschriftete Kanten entlanggehen und dabei gelegentlich den Ausgangspunkt wechseln. Wir wählen einen Knoten \(s\), an dem eine Kante anliegt, beginnen bei \(s\) und markieren \(s\) als besucht. Wir wenden die folgenden Regeln an:
- Falls am aktuellen Knoten eine unbeschriftete Kante anliegt, durchlaufen wir eine beliebige solche Kante, geben ihr die nächste Beschriftung \(1,2,\ldots,k\) und markieren den erreichten Knoten als besucht.
- Falls am aktuellen Knoten keine unbeschriftete Kante anliegt, aber anderswo noch unbeschriftete Kanten vorhanden sind, setzen wir den Kantenzug von einem besuchten Knoten aus fort, an dem eine unbeschriftete Kante anliegt.
Zunächst begründen wir, dass die zweite Regel stets anwendbar ist, wenn sie benötigt wird. Es sei \(W\) die Menge der besuchten Knoten. Jede beschriftete Kante hat beide Endknoten in \(W\). Läge an keinem Knoten in \(W\) eine unbeschriftete Kante an, so könnte es keine Kante zwischen \(W\) und seinem Komplement geben: Jede solche Kante müsste unbeschriftet sein. Da \(W\) nicht leer und \(G\) zusammenhängend ist, würde daraus folgen, dass jeder Knoten zu \(W\) gehört und somit keine unbeschrifteten Kanten mehr vorhanden sind – ein Widerspruch.
Die Konstruktion wird also fortgesetzt, bis alle \(k\) Kanten die verschiedenen Beschriftungen \(1,2,\ldots,k\) erhalten haben.
Nun sei \(v\) ein beliebiger Knoten, der zu mindestens zwei Kanten gehört.
Ist \(v=s\), so trägt eine an \(v\) anliegende Kante die Beschriftung \(1\), also ist der gesuchte größte gemeinsame Teiler gleich \(1\).
Ist \(v\neq s\), so betrachten wir den ersten Besuch von \(v\). Da ein Wechsel des Ausgangspunktes nur zu besuchten Knoten erlaubt ist, erfolgt dieser erste Besuch durch das Durchlaufen einer Kante, deren Beschriftung wir mit \(m\) bezeichnen. Vor diesem Durchlaufen war keine an \(v\) anliegende Kante beschriftet, denn beide Endknoten jeder beschrifteten Kante sind bereits besucht worden. Da an \(v\) mindestens zwei Kanten anliegen, liegt bei der Ankunft also noch eine unbeschriftete Kante an \(v\) an. Nach der ersten Regel wird unmittelbar eine solche Kante durchlaufen und mit \(m+1\) beschriftet.
Somit tragen zwei an \(v\) anliegende Kanten aufeinanderfolgende Zahlen als Beschriftungen. Der größte gemeinsame Teiler aller Beschriftungen an \(v\) teilt \[ \operatorname{ggT}(m,m+1)=1, \] ist also wie gefordert gleich \(1\). \(\square\)
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1991 · Soru 4
\(G\), \(k\) kenarlı bağlantılı bir çizge olsun. Kenarları \(1,2,\ldots,k\) ile, iki veya daha fazla kenarın birleştiği her köşede bu kenarlara verilen tam sayıların en büyük ortak böleni \(1\) olacak biçimde numaralandırmanın mümkün olduğunu kanıtlayınız.
[Bir çizge, köşe adı verilen bir noktalar kümesi ile farklı köşelerin bazı çiftlerini birleştiren kenarlardan oluşan bir kümeden meydana gelir. Her \(u,v\) köşe çifti en fazla bir kenara aittir. Her farklı \(x,y\) köşe çifti için, her \(v_i,v_{i+1}\) \((0\leq i<m)\) çifti \(G\)'nin bir kenarıyla birleştirilmiş olacak biçimde bir \(x=v_0,v_1,v_2,\ldots,v_m=y\) köşe dizisi varsa, \(G\) çizgesine bağlantılı denir.]
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
\(k=0\) ise kanıtlanacak bir şey yoktur. \(k\geq1\) olduğunu varsayalım.
Numaralandırılmamış kenarlar boyunca yürüyerek ve zaman zaman başlangıç noktasını değiştirerek bir numaralandırma oluşturacağız. Bir kenarın uç noktası olan bir \(s\) köşesi seçelim, \(s\)'den başlayalım ve \(s\)'yi ziyaret edilmiş olarak işaretleyelim. Aşağıdaki kuralları uygulayalım:
- Bulunulan köşeye bağlı numaralandırılmamış bir kenar varsa, bu kenarlardan herhangi biri boyunca ilerleyelim, bu kenara \(1,2,\ldots,k\) sırasındaki bir sonraki numarayı verelim ve ulaşılan köşeyi ziyaret edilmiş olarak işaretleyelim.
- Bulunulan köşeye bağlı numaralandırılmamış bir kenar yoksa, ancak başka yerlerde numaralandırılmamış kenarlar kalmışsa, kendisine bağlı numaralandırılmamış bir kenarı olan, daha önce ziyaret edilmiş bir köşeden yürümeye devam edelim.
Önce ikinci kuralın gerektiğinde her zaman uygulanabileceğini gösterelim. Ziyaret edilmiş köşeler kümesi \(W\) olsun. Numaralandırılmış her kenarın her iki uç noktası da \(W\)'dedir. \(W\)'deki hiçbir köşeye bağlı numaralandırılmamış bir kenar olmasaydı, \(W\) ile tümleyeni arasında hiçbir kenar bulunamazdı; çünkü böyle bir kenarın numaralandırılmamış olması gerekirdi. \(W\) boş olmadığından ve \(G\) bağlantılı olduğundan, bu durum her köşenin \(W\)'ye ait olduğunu ve dolayısıyla numaralandırılmamış hiçbir kenar kalmadığını gösterirdi; bu ise bir çelişkidir.
Böylece işlem, \(k\) kenarın tümüne birbirinden farklı \(1,2,\ldots,k\) numaraları verilene kadar devam eder.
Şimdi \(v\), en az iki kenarın birleştiği herhangi bir köşe olsun.
\(v=s\) ise, \(v\)'ye bağlı bir kenarın numarası \(1\) olduğundan, istenen en büyük ortak bölen \(1\)'dir.
\(v\neq s\) ise, bu köşenin ilk ziyaretini ele alalım. Başlangıç noktası yalnızca ziyaret edilmiş köşelerle değiştirilebildiğinden, bu ilk ziyaret bir kenar boyunca ilerlenerek gerçekleşir; bu kenarın numarası \(m\) olsun. Bu geçişten önce \(v\)'ye bağlı hiçbir kenar numaralandırılmamıştır; çünkü numaralandırılmış her kenarın her iki uç noktası da önceden ziyaret edilmiştir. \(v\)'ye bağlı en az iki kenar olduğundan, buraya varıldığında \(v\)'ye bağlı numaralandırılmamış bir kenar hâlâ vardır. Birinci kural gereği hemen böyle bir kenar boyunca ilerlenir ve bu kenara \(m+1\) numarası verilir.
Dolayısıyla \(v\)'ye bağlı iki kenarın numaraları ardışıktır. \(v\)'ye bağlı kenarların tüm numaralarının en büyük ortak böleni \[ \operatorname{ebob}(m,m+1)=1 \] sayısını böler; dolayısıyla istendiği gibi \(1\)'e eşittir. \(\square\)
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1991 · Problema 4
Sea \(G\) un grafo conexo con \(k\) aristas. Demostrar que es posible etiquetar las aristas con \(1,2,\ldots,k\) de tal manera que, en cada vértice que pertenezca a dos o más aristas, el máximo común divisor de los enteros que etiquetan esas aristas sea igual a \(1\).
[Un grafo consta de un conjunto de puntos, llamados vértices, junto con un conjunto de aristas que unen ciertos pares de vértices distintos. Cada par de vértices \(u,v\) pertenece a lo sumo a una arista. El grafo \(G\) es conexo si para cada par de vértices distintos \(x,y\) existe una sucesión de vértices \(x=v_0,v_1,v_2,\ldots,v_m=y\) tal que cada par \(v_i,v_{i+1}\) \((0\leq i<m)\) está unido por una arista de \(G\).]
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Si \(k=0\), no hay nada que demostrar. Supongamos que \(k\geq1\).
Construiremos un etiquetado recorriendo aristas sin etiquetar, con cambios ocasionales del punto de partida. Elijamos un vértice \(s\) incidente con una arista, comencemos en \(s\) y marquemos \(s\) como visitado. Apliquemos las siguientes reglas:
- Si el vértice actual tiene una arista incidente sin etiquetar, recorremos cualquiera de esas aristas, le asignamos la siguiente etiqueta \(1,2,\ldots,k\) y marcamos como visitado el vértice al que llegamos.
- Si el vértice actual no tiene ninguna arista incidente sin etiquetar, pero quedan aristas sin etiquetar en otra parte, reanudamos el recorrido desde un vértice visitado que tenga una arista incidente sin etiquetar.
Primero justificaremos que siempre es posible aplicar la segunda regla cuando se necesita. Sea \(W\) el conjunto de vértices visitados. Toda arista etiquetada tiene ambos extremos en \(W\). Si ningún vértice de \(W\) tuviera una arista incidente sin etiquetar, no podría haber ninguna arista entre \(W\) y su complemento: cualquiera de esas aristas estaría necesariamente sin etiquetar. Como \(W\) no es vacío y \(G\) es conexo, esto implicaría que todos los vértices pertenecen a \(W\) y, por consiguiente, que no queda ninguna arista sin etiquetar, lo cual es una contradicción.
Así, la construcción continúa hasta que las \(k\) aristas han recibido etiquetas distintas \(1,2,\ldots,k\).
Sea ahora \(v\) un vértice cualquiera que pertenezca al menos a dos aristas.
Si \(v=s\), una arista incidente con \(v\) tiene la etiqueta \(1\), por lo que el máximo común divisor requerido es \(1\).
Si \(v\neq s\), consideremos su primera visita. Como los cambios de punto de partida solo se permiten hacia vértices visitados, esta primera visita se produce al recorrer una arista, cuya etiqueta denotaremos por \(m\). Antes de recorrerla, ninguna arista incidente con \(v\) estaba etiquetada, pues ambos extremos de toda arista etiquetada ya han sido visitados. Como \(v\) tiene al menos dos aristas incidentes, al llegar a él todavía tiene una arista incidente sin etiquetar. La primera regla hace que recorramos inmediatamente una de esas aristas y la etiquetemos con \(m+1\).
Por tanto, dos aristas incidentes con \(v\) tienen etiquetas consecutivas. El máximo común divisor de todas las etiquetas en \(v\) divide a \[ \operatorname{mcd}(m,m+1)=1, \] por lo que es igual a \(1\), como se requería. \(\square\)
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1991 · 问题 4
设 \(G\) 是一个有 \(k\) 条边的连通图。证明：可以用 \(1,2,\ldots,k\) 给这些边标号，使得对于每个与两条或更多条边关联的顶点，这些边的标号的最大公因数等于 \(1\)。
[一个图由一组称为顶点的点，以及一组连接某些不同顶点对的边组成。每对顶点 \(u,v\) 至多由一条边连接。若对于每对不同的顶点 \(x,y\)，都存在一个顶点序列 \(x=v_0,v_1,v_2,\ldots,v_m=y\)，使得每对 \(v_i,v_{i+1}\) \((0\leq i<m)\) 都由 \(G\) 的一条边连接，则称图 \(G\) 是连通的。]
题目译自官方英文原文。 官方试卷 (PDF)
解答
若 \(k=0\)，则无须证明。以下假设 \(k\geq1\)。
我们沿尚未标号的边行走，并在必要时改变起点，以此构造一种标号方式。选择一个与某条边关联的顶点 \(s\)，从 \(s\) 出发，并将 \(s\) 记为已访问。按照以下规则进行：
- 若当前顶点有尚未标号的关联边，则沿任意一条这样的边行走，按 \(1,2,\ldots,k\) 的顺序给它标上下一个标号，并将到达的顶点记为已访问。
- 若当前顶点没有尚未标号的关联边，但别处仍有尚未标号的边，则从某个有尚未标号的关联边的已访问顶点重新开始行走。
首先说明，在需要使用第二条规则时，总能执行该规则。设 \(W\) 为已访问顶点的集合。每条已标号边的两个端点都在 \(W\) 中。若 \(W\) 中没有顶点具有尚未标号的关联边，则 \(W\) 与其补集之间不可能有边：因为任何这样的边必然尚未标号。由于 \(W\) 非空且 \(G\) 连通，这将意味着每个顶点都属于 \(W\)，从而不存在尚未标号的边，矛盾。
因此，这一构造可以持续进行，直到全部 \(k\) 条边分别获得互不相同的标号 \(1,2,\ldots,k\)。
现在任取一个与至少两条边关联的顶点 \(v\)。
若 \(v=s\)，则有一条与 \(v\) 关联的边的标号为 \(1\)，因此所要求的最大公因数为 \(1\)。
若 \(v\neq s\)，考虑第一次访问它的时刻。由于改变起点时只允许选择已访问的顶点，因此第一次访问它必然是沿某条边到达的，设这条边的标号为 \(m\)。在沿这条边行走之前，与 \(v\) 关联的边均未标号，因为每条已标号边的两个端点都已经被访问过。由于 \(v\) 至少有两条关联边，到达它时，它仍有一条尚未标号的关联边。根据第一条规则，接下来立即沿这样的一条边行走，并给它标号 \(m+1\)。
因此，有两条与 \(v\) 关联的边的标号是相邻整数。\(v\) 处所有边的标号的最大公因数整除 \[ \gcd(m,m+1)=1, \] 故它等于 \(1\)，符合要求。\(\square\)
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1991 · Задача 4
Пусть \(G\) — связный граф с \(k\) рёбрами. Докажите, что его рёбра можно пронумеровать числами \(1,2,\ldots,k\) так, чтобы в каждой вершине, принадлежащей двум или более рёбрам, наибольший общий делитель номеров этих рёбер был равен \(1\).
[Граф состоит из множества точек, называемых вершинами, и множества рёбер, соединяющих некоторые пары различных вершин. Каждая пара вершин \(u,v\) принадлежит не более чем одному ребру. Граф \(G\) называется связным, если для каждой пары различных вершин \(x,y\) существует последовательность вершин \(x=v_0,v_1,v_2,\ldots,v_m=y\), в которой каждая пара \(v_i,v_{i+1}\) \((0\leq i<m)\) соединена ребром графа \(G\).]
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Если \(k=0\), доказывать нечего. Предположим, что \(k\geq1\).
Построим нумерацию, проходя по непронумерованным рёбрам и время от времени меняя начальную вершину обхода. Выберем вершину \(s\), инцидентную какому-либо ребру, начнём обход из \(s\) и объявим \(s\) посещённой. Будем применять следующие правила:
- Если у текущей вершины есть непронумерованное инцидентное ребро, пройдём по любому такому ребру, присвоим ему очередной номер \(1,2,\ldots,k\) и объявим достигнутую вершину посещённой.
- Если у текущей вершины нет непронумерованных инцидентных рёбер, но в графе ещё остались непронумерованные рёбра, продолжим обход из посещённой вершины, имеющей непронумерованное инцидентное ребро.
Сначала обоснуем, что второе правило всегда можно применить, когда это необходимо. Пусть \(W\) — множество посещённых вершин. Оба конца каждого пронумерованного ребра принадлежат \(W\). Если бы ни у одной вершины из \(W\) не было непронумерованного инцидентного ребра, то между \(W\) и его дополнением не было бы рёбер: любое такое ребро обязательно было бы непронумерованным. Поскольку \(W\) непусто, а \(G\) связен, отсюда следовало бы, что все вершины принадлежат \(W\) и, следовательно, непронумерованных рёбер не осталось, — противоречие.
Таким образом, построение продолжается, пока все \(k\) рёбер не получат различные номера \(1,2,\ldots,k\).
Теперь пусть \(v\) — любая вершина, принадлежащая по крайней мере двум рёбрам.
Если \(v=s\), то одно из рёбер, инцидентных \(v\), имеет номер \(1\), поэтому требуемый наибольший общий делитель равен \(1\).
Если \(v\neq s\), рассмотрим её первое посещение. Поскольку менять начальную вершину обхода разрешается только на уже посещённую вершину, первое посещение \(v\) происходит при проходе по некоторому ребру, пусть его номер равен \(m\). До этого прохода ни одно ребро, инцидентное \(v\), не было пронумеровано, поскольку оба конца каждого пронумерованного ребра уже посещены. Так как вершине \(v\) инцидентны по крайней мере два ребра, после прихода в неё у неё остаётся непронумерованное инцидентное ребро. По первому правилу мы сразу проходим по такому ребру и присваиваем ему номер \(m+1\).
Следовательно, два ребра, инцидентные \(v\), имеют последовательные номера. Наибольший общий делитель всех номеров рёбер при вершине \(v\) делит \[ \operatorname{НОД}(m,m+1)=1, \] поэтому он равен \(1\), что и требовалось. \(\square\)
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1991 · المسألة 4
افترض أن \(G\) رسم بياني متصل له \(k\) ضلعًا. أثبت أنه يمكن ترقيم الأضلاع بالأعداد \(1,2,\ldots,k\) بحيث يكون، عند كل رأس ينتمي إلى ضلعين أو أكثر، القاسم المشترك الأكبر للأعداد التي ترقم تلك الأضلاع مساويًا لـ\(1\).
[يتكون الرسم البياني من مجموعة من النقاط، تسمى رؤوسًا، مع مجموعة من الأضلاع تصل بين بعض أزواج الرؤوس المختلفة. وينتمي كل زوج من الرؤوس \(u,v\) إلى ضلع واحد على الأكثر. ويكون الرسم البياني \(G\) متصلًا إذا وجدت، لكل زوج من الرؤوس المختلفة \(x,y\)، متتالية من الرؤوس \(x=v_0,v_1,v_2,\ldots,v_m=y\) بحيث يصل بين كل زوج \(v_i,v_{i+1}\) \((0\leq i<m)\) ضلع من \(G\).]
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
إذا كان \(k=0\)، فلا شيء يحتاج إلى إثبات. لنفترض أن \(k\geq1\).
ننشئ ترقيمًا بالسير على أضلاع غير مرقمة، مع تغيير نقطة البداية من حين إلى آخر. نختار رأسًا \(s\) ينتمي إلى ضلع، ونبدأ عند \(s\)، ونعدّ \(s\) رأسًا تمت زيارته. نطبق القاعدتين الآتيتين:
- إذا كان الرأس الحالي ينتمي إلى ضلع غير مرقم، نعبر أي ضلع من هذا القبيل، ونعطيه الرقم التالي من \(1,2,\ldots,k\)، ونعدّ الرأس الذي وصلنا إليه رأسًا تمت زيارته.
- إذا لم يكن الرأس الحالي ينتمي إلى أي ضلع غير مرقم، ولكن بقيت أضلاع غير مرقمة في مواضع أخرى، نستأنف السير من رأس تمت زيارته وينتمي إلى ضلع غير مرقم.
نبرر أولًا إمكان تطبيق القاعدة الثانية كلما دعت الحاجة إليها. لتكن \(W\) مجموعة الرؤوس التي تمت زيارتها. طرفا كل ضلع مرقم ينتميان إلى \(W\). لو لم يكن أي رأس في \(W\) ينتمي إلى ضلع غير مرقم، لما أمكن وجود ضلع بين \(W\) ومتممتها: إذ إن أي ضلع من هذا القبيل سيكون بالضرورة غير مرقم. وبما أن \(W\) غير خالية وأن \(G\) متصل، فإن ذلك يستلزم أن كل رأس ينتمي إلى \(W\)، وبالتالي أنه لم تبق أضلاع غير مرقمة، وهذا تناقض.
إذن يستمر الإنشاء حتى تحصل الأضلاع الـ\(k\) كلها على الأرقام المختلفة \(1,2,\ldots,k\).
ليكن الآن \(v\) أي رأس ينتمي إلى ضلعين على الأقل.
إذا كان \(v=s\)، فإن أحد الأضلاع التي ينتمي إليها \(v\) يحمل الرقم \(1\)، لذا فإن القاسم المشترك الأكبر المطلوب هو \(1\).
إذا كان \(v\neq s\)، فلننظر إلى زيارته الأولى. بما أن تغيير نقطة البداية مسموح به فقط إلى رؤوس تمت زيارتها، فإن هذه الزيارة الأولى تحدث بعبور ضلع، وليكن رقمه \(m\). قبل هذا العبور، لم يكن أي ضلع ينتمي إليه \(v\) مرقمًا، لأن طرفي كل ضلع مرقم قد تمت زيارتهما بالفعل. وبما أن \(v\) ينتمي إلى ضلعين على الأقل، فإنه عند الوصول إليه يظل ينتمي إلى ضلع غير مرقم. تقضي القاعدة الأولى بعبور ضلع من هذا القبيل مباشرة وترقيمه بالعدد \(m+1\).
ومن ثم فإن ضلعين ينتمي إليهما \(v\) يحملان رقمين متتاليين. والقاسم المشترك الأكبر لجميع الأرقام عند \(v\) يقسم \[ \gcd(m,m+1)=1, \] لذا فهو يساوي \(1\)، كما هو مطلوب. \(\square\)
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).