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)$.


Note: a *spanning subgraph* of a graph $G=(V,E)$ is a graph $G\_X=(V,X)$, where $X \subseteq E$.


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.



Alternative proof for counting problem in graphs
I think I have a proof. I take it kind of pedantically because I am a little suspicious that it looks both simple in ideas and convoluted in details, but see what you thnk . Following that are very preliminary comments on inductive proofs. 


We think of graphs as sets of edges. I will change the notation slightly to have $D'(G,H)$ and $D( G, \vec H)$ denote the things they previously counted. So our goal is to show $|D'(G,H)| \le |D(G, \vec H)|.$ 


Given a subgraph $S$ of $G$ with a possible orientation, let $\operatorname{emb}(H,S)$ and $\operatorname{emb}(\vec H,\vec S)$ be the sets of embeddings of of $H$ in $S$ which ignore and respect the orientations. The key to my proof is the observation $|\operatorname{emb}(H,S)| \ge |\operatorname{emb}(\vec H,\vec S)|$ so that , when both are positive, $$\frac{1}{|\operatorname{emb}(H,S)|} \le \frac{1}{|\operatorname{emb}(\vec H,\vec S)|}.$$ 


Consider the various triples $(\vec G,S,f) \in D(G, \vec H) \times D'(G,H) \times \operatorname{emb}(H,G).$ So each consists of an orientation of $G$, a distinguished subset $S$ (which inherits an orientation $\vec S$) and an embedding of $H$ into $G$. Call such a triple *viable* when the embedded copy of $H$ is inside $S$ and the orientation that it gets from $\vec G$ is the one specified in the problem. We will weight the viable triples in two ways so that they sum to the two quantities we wish to compare, one will depend only on the set $S$ and the other on both the set $S$ and the orientation $\vec G$. 


First count the viable triples with various restrictions. 


For each fixed $f \in \operatorname{emb}(H,G),$ The number of viable triples $(\cdot,\cdot,f)$ is $(2^{|G|-|H|})^2$ Because the $H$ edges already chosen are going to be in $S$ and already have their orientation in $\vec G$ determined. For each other edge we must decide both which orientation it will get and also if it will or will not be in $S$.


For each fixed subgraph $S \in D'(G,H)$, the number of viable triples $(\cdot,S,\cdot)$ is $|\operatorname{emb}(H,S)|2^{|G|-|H|}$ because we still need an embedding and then it remains to orient all the edges not already determined.


For a fixed orientation $\vec G \in D(G,\vec H)$ it is slightly more involved. If we also fix the embedding $f$ viably, then there are $2^{|G|-|H|}$ ways to pick all, some or none of the other edges for $S$. But if we fix $\vec G$ and $S$ then the number of compatible embeddings is $|\operatorname{emb}(\vec H,\vec S)|.$


So, if we want the sum to come to $|D'(G,H)|$ then each viable triple $(\vec G,S,f)$ should get the weight $\frac{1}{|\operatorname{emb}(H,S)|2^{|G|-|H|}}.$ However, if we want the weights to sum to $|D(G, \vec H)|,$ then each viable triple $(\vec G,S,f)$ should get the weight $\frac{1}{|\operatorname{emb}(\vec H,\vec S)|2^{|G|-|H|}}.$ As remarked above, this establishes $|D'(G,H)| \le |D(G, \vec H)|$ because the weights we sum have $\frac{1}{|\operatorname{emb}(H,S)|2^{|G|-|H|}} \le \frac{1}{|\operatorname{emb}(\vec H,\vec S)2^{|G|-|H|}}$


**Comments on potential inductive proofs** 


When $H$ is a single oriented edge we have $D'(G,H)=2^{|G|}-1$ because we can take $S$ to be any nonempty subset of edges. This is just one less than $D(G, \vec H)=2^{|G|}$ because all the orientations are fine. So this suggests one approach: Fix $G$ and then build $\vec H$ one oriented edge at a time. 


Swapping roles, another approach is to fix $H$ and build $G$ starting at $H.$ Clearly $D'(H,H)=1$, we need all the edges. But $D(H,\vec H) \ge 1$ because there is certainly at least one viable orientaation. I suppose it depends on if $\vec H$ has any automorphisms.


Finally, in any case we can assume that every edge of $G$ is used in at least one embedding of $H$ into $G.$ Any other edge can be oriented either way and can be included or not in a possible subset. Accordingly, $D'(G,H)=2D'(\hat G,H)$ and $D(G,\vec H)=2D(\hat G,\vec H)$ where $\hat G$ is just $G$ with the useless edge removed.


