Graph Theory

  • Thread starter pupeye11
  • Start date
  • #1
100
0

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:

[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


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.
 

Answers and Replies

  • #2
402
1
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.
 
  • #3
100
0
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?
 
  • #4
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,631
641
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
 
  • #5
100
0
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.
 

Related Threads on Graph Theory

  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
0
Views
900
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
2
Views
917
Replies
2
Views
2K
  • Last Post
Replies
0
Views
5K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
8
Views
2K
Top