Skip to main content
2 of 3
deleted 20 characters in body; added 11 characters in body

Alternative proof for counting problem in graphs

Let $G$ and $H$ be graphs, let $\vec H$ be a fixed orientation of $H$.

Denote by $D(G,\vec H)$ the number of orientations of $G$ that contain a copy of $\vec H$ and denote by $D'(G,H)$ the number of spanning subgraphs of $G$ that contain a copy of $H$.

Claim: $D'(G,H) \leq D(G, \vec H)$.

In [1] the claim is proven using some more general results involving set systems and shattering. Is there a simple, elementary (e.g. inductive) proof of the result?

[1] L.Kozma, S.Moran: Shattering, Graph Orientations, and Connectivity, 2012.