World's most popular travel blog for travel bloggers.

Equivalent definitions for subgraph

, , No Comments
Problem Detail: 

I know that a graph G' is a subgraph for G if V(G')⊆V(G) and E(G')⊆E(G).

Today my professor wrote that G' is a subgraph for G if G' is a graph and V(G')⊆V(G), and then he told us that this definition is equivalent to the one we've seen before (= the first line in this post).

However, I don't think that these definitions are equivalent. In fact, if this is G:

       2      /   \     1     3 

and this is G':

    1 - 3 

we have that G' is a subgraph for G according to the second definition (wrong), while it is not according to the first one (right).

Am I missing something or was the professor wrong?

Asked By : A. C.
Answered By : David Richerby

The alternative definition that you attribute to your professor is wrong, as your counterexample clearly shows.

I hope your professor actually said something else and you misunderstood him/her!

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback