# Is a subgraph either a spanning subgraph or a full subgraph?

A graph $G' = (N' ,A')$ is a spanning subgraph of a graph $G = (N, A)$ iff $N ' = N$ and $A' \subseteq A$.

A graph $G' = (N',A')$ is a full subgraph of a graph $G = (N, A)$ iff $N' \subseteq N$ and $A' = \{(x,y) \in A \mid x,y \in N '\}$.

• I have to prove that "If $G'$ is a subgraph of a graph $G$, then either G' is a spanning subgraph of $G$, or $G'$ is a full subgraph of $G$. If this statement is valid, provide a proof that it is valid, otherwise provide a counterexample" but isn't a full subgraph actually a spanning subgraph?

I mean that any subgraph of $G$ is a full subgraph in the end, right? Any ideas how I can prove the statement?

• My second question is how to calculate the number of spanning subgraphs of $G$ as a function of the number of nodes in $N$. How can I do this without knowing $A$ or how many edges I have in the graph?
• Also, it might be good to write what do you mean by subgraph. because in the usual sense: $(N',A')$ is a subgraph of $(N,A)$ when $N' \subseteq N$ and $A' \subseteq A$. If this is the case, then what you called 'full subgraph' is not actually a 'subgraph' in the usual sense because it can have edges not present in the original graph. – Apiwat Chantawibul Apr 23 '15 at 20:35
• @Billiska yes, it reflects what I meant . Actually the full subgraph will be a subgraph of G because I said that (x,y) ∈ A (which means from any pair of edges in the original graph - A ) I cannot add any new edges because then the pair won't belong to A. And a subgraph G'=(N',A') is a graph of G=(N,A) where N′⊆N and A'⊆A – KeykoYume Apr 23 '15 at 21:52
• You're right about that. then, I am undeleting my answer. it should be valid now. – Apiwat Chantawibul Apr 23 '15 at 22:37
• I suggest you make the question more focused. If you have multiple questions, it is better to make multiple questions. – Juho May 24 '15 at 8:56

On your second question "how to calculate the number of spanning subgraphs of $G$ as a function of number of nodes in $N$." Since it is a fact that graph $G = (N,A)$ with differing $A$ will have differing number of possible spanning subgraphs, I suspect you might have misunderstood the question. For example, does the question actually only ask for an upper bound of the number of possible spanning subgraphs as function of $|N|$?