Home > Blockchain >  Is a single node after dividing a graph still considered a subset?
Is a single node after dividing a graph still considered a subset?

Time:12-08

For example: enter image description here

Dividing between A and B: enter image description here

Would DAC and B be considered two subsets?

I am trying to create two subsets from an initial graph of 4 nodes.

CodePudding user response:

"A graph G is a finite nonempty set of objects called vertices together with a possibly empty set of unordered pairs of distinct vertices of G called edges."

"A graph H is a subgraph of a graph G if V(H) is a subset of V(G) and E(H) is a subset of E(G)"

-- both from Graph & Digraphs 2nd ed by Chartrand & Lesniak.

DAC and B are both subgraphs of the input graph. Neither is a subset since a graph isn't a set but a pair of sets as defined above. Note as per the definitions, a graph can have no edges, but must have at least one vertex.

CodePudding user response:

I'm guessing by subset you mean subgraph.

The answer is yes, a single isolated node is still a subgraph of the graph that contains that node.

Subgraphs can even be empty. The empty graph is a subgraph of all graphs.

  • Related