MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G=(V,E)$ be a graph where every "internal" vertex has degree 4, and every "external" vertex has degree $\le 3$. What can be said about this graph if it can be covered by a collection of edge-disjoint paths connecting internal vertices with external vertices? Did anybody study such problem? What are the possible obstructions? The question is related to amenability of the R.Thompson group $F$ (an approach of Victor Guba).

Clarification. For every internal vertex, one needs to choose a path connecting it to an external vertex, and all these paths (together) should be edge disjoint. You can view it as an evacuation plan. We need to evacuate all internal vertices using edges as bridges, but every edge can be used at most once.

share|cite|improve this question
Do you mean that some of the vertices are called "internal" and they have degree 4 and the rest are called "external" and have degree at most 3, or do "internal" and "external" have some more meaning? – Péter Komjáth Oct 19 '10 at 12:04
These would be planar graphs? and your paths would have external vertices for its endpoints, internal for all the other points? And covering means using every edge in the graph exactly once? – Gerry Myerson Oct 19 '10 at 12:06
Perhaps your "internal"/"external" nomenclature comes from the graph being a lattice-graph of size $m \times n$, which would have $(m-1)(n-1)$ vertices of degree $4$ internally, $2m+2n-4$ vertices of degree $3$ externally along the edges, and $4$ vertices of degree $2$ externally at the corners of the lattice. Is this the particular type of graph you're considering in this problem? – sleepless in beantown Oct 19 '10 at 12:08
@Peter Komjath: there are two kinds of vertices: internal and external. These are just names for vertices of degree 4 and vertces of degree 3, respectively. @Gerry: No, these are not planar graphs, far from it. @Sleepless: No, the graph is related to the Cayley graph of $F$ with respect to a certain set of generators. So it is infinite, in particular (but finite finite subgraphs are also interesting). Non-existence of the cover would imply non-amenability. It is too long to explain how. But that is why obstructions are of interest. – Mark Sapir Oct 19 '10 at 14:07

Your Answer


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

Browse other questions tagged or ask your own question.