Grap theory question, please help

Question

let G=(V,E) be a graph where V={A⊆N₅||A|=2}

and E={{A,B}⊆V|A∩B=ø}

sketch this graph and find its size

Answer 1

Hello Kyle,

 

Just to make sure I understand the problem, by N₅ do you mean the null graph on five vertices?  

 

If so, the set V would contain all the possible pairs of vertices from a set of five vertices.  The standard description of a graph has the vertex set consist of individual points, so in your problem, we are dealing with a more generalized form for each vertex; namely, as a pair of "primitive" points.  

 

If we accept the vertices as pairs of nodes from N₅, we must then make sense of your edge set.  But the way you have written it, the edge set contains subsets of V, and these are written in a way to evoke the individual pairs of points from N₅ in the intersection condition.  This should not happen in the standard definition of a graph (since the intersections would all be empty), so something is amiss in your description of the problem.

 

My guess is that the problem may have been intended to look like this:

 

"Let G = (V,E) be a graph where

 

V = {A⊆N₅ | |A|=2}

 

and

 

E = {{A,B} | A,B⊆V and A∩B=∅}.

 

Sketch this graph and find its size."

 

Note the subtle difference in the definition of the edge set E.  

 

If we accept my revision of the problem (and, of course, there is no reason to do so if you don't agree with it!), we come to the following solution:

 

For every pair in V, there exists an edge between it and any other pair in V as long as these pairs are disjoint.  Count the number of pairs in V; that is, compute |V|.  Evidently, |V| = ₅C₂ = 10.  

 

Now, figure out how many of the pairs in V are disjoint.  If we name the nodes in N₅ generically 1,2,...,5, then for instance, {1,2} is disjoint from {3,4}, {3,5}, and {4,5} only.  Continuing in this way, and making sure not to double-count any disjoint pairs, we find that there are a total of 15 disjoint pairs in V (3⋅10/2 = 15).  But these correspond to the edges of the graph G, so its size is 15.

 

Regards,

Hassan