MathDB

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 Statement