1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory

  1. Jun 21, 2010 #1
    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:

    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

    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.
  2. jcsd
  3. Jun 21, 2010 #2
    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.
  4. Jun 21, 2010 #3
    Ok, thats 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?
  5. Jun 21, 2010 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    By |A and B| I suspect you mean

    [tex] | A \cap B |[/tex] which is the number of elements contained in both A and B. In this case

    [tex]A \cap B = \{ 1 \}[/tex] because 1 is the only element contained in both A and B. So [tex]\ |A \cap B| = | \{ 1 \} | = 1[/tex] 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
  6. Jun 21, 2010 #5
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook