# 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. Commented Apr 23, 2015 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 Commented Apr 23, 2015 at 21:52
• You're right about that. then, I am undeleting my answer. it should be valid now. Commented Apr 23, 2015 at 22:37
• I suggest you make the question more focused. If you have multiple questions, it is better to make multiple questions.
– Juho
Commented May 24, 2015 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|$?