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:

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

    Office_Shredder

    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