Let $G$ be a simple undirected graph with vertices $v_1,v_2,...,v_n$. We denote the number of acyclic orientations of $G$ with $f(G)$. a) Prove that $f(G)\le f(G-v_1)+f(G-v_2)+...+f(G-v_n)$. b) Let $e$ be an edge of the graph $G$. Denote by $G'$ the graph obtained by omiting $e$ and making it's two endpoints as one vertex. Prove that $f(G)=f(G-e)+f(G')$. c) Prove that for each $\alpha >1$, there exists a graph $G$ and an edge $e$ of it such that $\frac{f(G)}{f(G-e)}<\alpha$. Proposed by Morteza Saghafian
Problem
Source: Iran 3rd round 2012-Final exam-P1
Tags: combinatorics proposed, combinatorics
20.09.2012 18:05
a) For each acyclic orientation of $G$, we'll prove there exists a vertex $v_i$ such that it's outer degree is zero. To prove this, suppose the statement is not true, and starting with $v_1$, each time go from a vertex $v$ to $u$ whenever there exists an edge from $v$ to $u$. Since there are only finitely many vertices in this graph, we'll find an oriented cycle, which is a contradiction. Now by knowing this, it's easy to prove that $f(G)\le f(G-v_1)+f(G-v_2)+...+f(G-v_n)$.
03.03.2013 21:19
b) For any acyclic orientation of $E - e$, we claim there is at least one way to orient $e$ such that the resulting graph is acyclic. Let $e$ be directed from $v_i$ to $v_j$ and suppose, for the sake of contradiction, that both for orientations of $e$ the resulting graph would contain a cycle. Then there must exist cycles \[v_{a_1}v_{a_2} \dots v_iv_j v_{a_m} \dots v_{a_1}\] \[v_{b_1}v_{b_2} \dots v_jv_i v_{b_n} \dots v_{b_1}\] This forces the cycle \[v_{a_1}v_{a_2}\dots v_i v_{b_n} \dots v_{b_1} v_{b_2} \dots v_j v_{a_m} \dots v_{a_1}\] which uses edges entirely from $E - e$, contradicting the fact that these edges were oriented acyclically. Then $f(G) = f(G - e) + N$, where $N$ denotes the number of acyclic orientations of $E - e$ in which either orientation of $e$ leaves the resulting graph acyclic. It is easy to see this occurs if and only if for every vertex $v \in V - \{v_i, v_j\}$ either both edges $vv_i$ and $vv_j$ (if they exist) are directed away from $v$ or both edges are directed towards $v$. This is the same as the number of acyclic orientations of $G$ after contracting edge $e$, which is $f(G')$. Thus $f(G) = f(G - e) + f(G')$. c) Consider the following graph $G$ on $n + 2$ vertices: take two vertices $v_x$ and $v_y$ and join them by an edge. Then for $1 \le i \le n$, draw exactly two edges from $v_i$, one to $v_x$ and one to $v_y$. We take $e = v_xv_y$. We want \[\frac{f(G)}{f(G - e)} = \frac{f(G - e) + f(G')}{f(G - e)} = 1 + \frac{f(G')}{f(G - e)}\] to get arbitrarily close to $1$. We established above that $f(G')$ represents the number of acyclic orientations of $E - e$ for which any orientation of $e$ keeps the graph cycle-free. For our $G$, this is clearly $2^{n}$; if for any vertex $v \ne v_x, v_y$ the edges $vv_x$ and $vv_y$ pointed in opposite directions, we could orient $v_xv_y$ in such a way that $vv_xv_y$ would be a cycle. On the other hand, $f(G - e)$ represents the total number of acyclic orientations of $E - e$. We claim this equals $2\cdot3^{n} - 2^{n}$. For each of the two possible orientations of $e$, the number of acyclic orientations of $E - e$ for which the chosen orientation of $e$ keeps the graph cycle-free is $3^n$, since we can orient the pair of edges $vv_x, vv_y$ in all but one way (the way which would make $vv_xv_y$ a cycle). It is easy to see that this is both necessary and sufficient for $G$ to be acyclic. However, we have overcounted those orientations of $E - e$ for which either orientation of $e$ will keep the graph cycle-free; we just established that this number is $2^{n}$. Then \[\frac{f(G)}{f(G - e)} = 1 + \frac{2^{n}}{2\cdot3^{n} - 2^{n}}\] For $n$ sufficiently large, the second term gets as close to $0$ as we like, so for all $\alpha > 1$ such a graph exists.