(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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:

[tex]

V = nCr(X,2) or nCr(X,3)

E = {{A,B}:A,B\inV and |A\capB|=2}

[/tex]

(a) Draw the diagram of the graph G

(b) Use Theorem (*) to show that G is Eulerian.

(c) Exhibit an Euler circuit

2. Relevant 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.

3. 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Graph Theory

**Physics Forums | Science Articles, Homework Help, Discussion**