1
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Apiwat Chantawibul Apr 23 '15 at 20:35
  • $\begingroup$ @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 $\endgroup$ – KeykoYume Apr 23 '15 at 21:52
  • $\begingroup$ You're right about that. then, I am undeleting my answer. it should be valid now. $\endgroup$ – Apiwat Chantawibul Apr 23 '15 at 22:37
  • 1
    $\begingroup$ I suggest you make the question more focused. If you have multiple questions, it is better to make multiple questions. $\endgroup$ – Juho May 24 '15 at 8:56
2
$\begingroup$

On your question "isn't a full subgraph actually a spanning subgraph?". The answer is no, a full subgraph doesn't need to be a spanning subgraph. By your definition, a full subgraph can have lesser number of vertices than in the original graph. However, a spanning subgraph must have exactly the same set of vertices in the original graph.

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|$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.