Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

enter image description here

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: enter image description here . The following transformation is also allowed where the blue has label $k$, red has label $k+1$ and green had label $k+2$:

enter image description here

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.

share|improve this question
1  
Very hard to understand. How can a graph have a component without vertices? What is the meaning of "neighboring edges"? What is the meaning of "congruent label"? How can two vertices be joined by two edges --- does this mean you are permitting multiple edges? You refer to sliding vertices, but the diagrams appear to show sliding edges. Are you really dealing with graphs, or with particular diagrams of graphs? This question needs a lot of work before it is comprehensible. –  Gerry Myerson Nov 20 '12 at 23:12
2  
@Gerry 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. If you could with rewording given this that would be great! –  George Krasilnikov Nov 20 '12 at 23:21
1  
Good. What are "adjacent edges"? Are these edges that share a vertex? Please edit the question to reflect the clarifications you have made in the comments. –  Gerry Myerson Nov 20 '12 at 23:34
2  
@GerryMyerson What is meant by adjacent here is that the edges in question 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. –  George Krasilnikov Nov 22 '12 at 6:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.