Number of vertices in a Graph given two sets

33 Views Asked by At

I stumbled upon a sample question, while learning about graph theorie (discrete mathematics), but I can't quite solve it. Definiton of a graph (undirected): $G := (V,E)$

Def of V and E:

$V := \{A \subseteq \{1, . . . n\} \mid |A| \in \{1, n − 1\}\}$

$E := \{\{A, B\} \mid A, B \in V, A \neq B, A \subseteq B\}$

I want to draw the graph, so I need the number of vertices.

Let's say n = 3:

Is V = {1,2,3} and E = {{1,2}, {1,3}, {2,3}} ?

1

There are 1 best solutions below

0
On BEST ANSWER

No. The vertices are all subsets of $\{1,2,3\}$, not including $\varnothing$ or the whole set. So $$V=\{\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\}\}.$$

Now you put an edge between two vertices if one of their sets is a subset of the other. We can draw this with the vertices at different levels depending on the size of their set:

enter image description here