Exploring a Graph with X={1,2,3,4} and G=(V,E)

[pupeye11]

Homework Statement

Let X = {1,2,3,4} and let G = (V,E) be the graph whose vertices are the 2-element and 3-element subsets of X and where A is adjacent to B if |A and B| = 2. That is:

$$V = nCr(X,2) or nCr(X,3) E = {{A,B}:A,B\inV and |A\capB|=2}$$

(a) Draw the diagram of the graph G
(b) Use Theorem (*) to show that G is Eulerian.
(c) Exhibit an Euler circuit

Homework Equations

(*) Let G be a connected general graph. Then G has a closed Eulerian trail if and only if the degree of each vertex is even.

The Attempt at a Solution

Well the 2-element subsets of X are {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}.
and the 3-element subsets of X are {1,2,3},{1,3,4},{1,2,4},{2,3,4}.

How can these be vertices? And would this be more than one graph? I am confused by this.

 

[JSuarez]

Picture a 10-vertex graph, where each vertex is labelled by one of those sets. Then you must determine which ones are adjacent, and this reduces to the question of how many (non-ordered) pairs of those sets have exactly two elements in common.

 

[pupeye11]

Ok, that's what I figured but I how would I find |A and B|? Is there some kind of ordered pair subtraction I am forgetting about or something?

For example if I take A = {1,2} and B = {1,3} how do I find what |A and B| is? Does the method also work if I was to replace B with a 3-element set?

 

[Office_Shredder]

By |A and B| I suspect you mean

$$| A \cap B |$$ which is the number of elements contained in both A and B. In this case

$$A \cap B = \{ 1 \}$$ because 1 is the only element contained in both A and B. So $$\ |A \cap B| = | \{ 1 \} | = 1$$ because there is only one element in the set.

It doesn't matter what your original sets A and B are, all you need to do is see how many elements they have in common

 

[pupeye11]

Ok, so after getting the diagram, if I use that theorem to show G is Eulerian it is as easy as saying since G is a connected graph where the 2-element vertices have a degree of 2 while the 3-element vertices have a degree of 4 so they all have an even number of vertices making it Eularian.

Then for (c) I am assuming that a Euler Circuit is a path that passes over each edge exactly once.