Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed.
Consider any planar graph that is not necessarily connected, but that might have connected components consisting of circles without vertices. Each edge of the graph is labelled with a positive integer $(1,2,...n)$ for fixed $n$. We can classify the vertices in this sort of graph in two ways. The first class of vertex is that which has degree 6, with the labels of incoming edges alternating between $k$ and $k+1$ for $k\in (1,2,3...n-1)$. The other class of vertex has degree 4 with labels of the incoming edges going $i,j,i,j,...$ for $i,j, \in (1,2,...n)$ and where $i$ and $j$ differ by more than $1$.
Two such graphs are equivalent iff related by the following rules/equivalences:
. Circles with nothing in their loops can be removed;
. Neighboring(adjacent) edges of congruent label can be altered in the following fashion:
What is meant by adjacent here is that the edges both bound the same region. In other words, one can draw a line segment on the plane which meets the graph only in those two edges.The adjacent edges need not share a vertex. In fact, if they have the same label, they can not share a vertex.
.If two vertices of degree four(the second class of vertex mentioned) are connected by two edges both "2nd class vertices" can be removed. Similarly if two first class vertices are connected by two edges both vertices can be removed.
. A sequence of 2nd class vertices can be slid to the other side of a first of second class vertice: . The following transformation is also allowed where the blue has label $k$, red has label $k+1$ and green had label $k+2$:
How can we prove that all such graphs are equivalent to the null graph? (I think it is evident that the approach involves induction on $n$. I also think looking at the subgraph for any given graph involving only edges labelled with $k$ would be productive. In particular I think it would be productive to examine what this subgraph looks like if $k$ is not involved with $1st$ and $2nd$ class vertices, respectfully... how can we get rid of the subgraph involving only $k$ edges using the equivalency relations?)
I am posting clarifications that I made in response to Gerry's comment: vertices are classified by the edges they connect to so by sliding vertices, I did mean sliding edges. Yes, multiple edges are allowed. By neighboring edges I mean adjacent edges- ie adjacent edges with the same label can be "transformed"/altered in the way shown. We are permitting multiple edges, yes.
What is meant by adjacent here is that the edges both bound the same region. In other words, one can draw a line segment on the plane which meets the graph only in those two edges.The adjacent edges need not share a vertex. In fact, if they have the same label, they can not share a vertex.