Consider triangulation $T.$
Is it always possible to choose such a subgraph $H$ of $T$ that has a common edge with every face of $T$ and can be directed in such way that indegrees of all vertices of $H$ are equal to one?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ It might depend on what you're triangulating. If the triangulation is of a surface of genus $g > 1$, the answer is "no" by a counting argument. Let $F$ be the number of triangles (faces) of your triangulation, then the number of edges is $E = 3/2 F$ and the number of vertices is $E-F+(2-2g) < F/2$. The number of edges in $H$ must be bounded above by the number of vertices and below by $F/2$, which is a problem. For the remaining cases, you might find this question useful: mathoverflow.net/questions/112661/… $\endgroup$– Elena YudovinaCommented May 19, 2016 at 14:02
-
$\begingroup$ Triangulation which I consider is on the plane. I saw that another question about spanning tree, but what if we need just spanning forest or spanning forest with some cycles which are not connected? $\endgroup$– WalkiriaCommented May 20, 2016 at 6:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The answer is "no" even in the plane.
Here's the intuition (which was also my search algorithm). Having an edge adjacent to every face is equivalent to an edge covering of the dual graph. A triangulation in the plane (strictly speaking, on the sphere) will have $E = 3/2 F$ and therefore $V=2+F/2$; this is the upper bound on the number of edges in $H$. So in the dual graph you're looking for an edge covering of size at most $2 + \tilde V/2$ (where $\tilde V = F$ is the number of vertices in the dual graph). Since the sum of the size of the minimum edge cover and the size of the maximum matching are equal to the number of vertices, to find a counterexample it suffices to find a 3-regular planar graph with small maximum matching size (less than $\tilde V/2 - 2$), and then take its dual.
The graph in Figure 7 of Biedla, Demaine, Duncan, Fleischerd, Kobourove "Tight bounds on maximal and maximum matchings" (Discrete Mathematics 2004, vol. 285, p. 7-15, online at http://www.sciencedirect.com/science/article/pii/S0012365X04002304) is planar (uncross the crossings at the bottom), 3-regular, with 88 vertices and maximal matching of size 39. Its dual then is a triangulation that won't have a subgraph $H$ that you describe.
