Problem

Source: Iran 3rd round 2012-Final exam-P1

Tags: combinatorics proposed, combinatorics



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