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

  • Thread starter pupeye11
  • Start date
  • Tags
    Graph
In summary: In this case if I draw a path from A to B, and then from B to C, then the path from A to C would be on the Euler Circuit, and the path from B to C would not.
  • #1
pupeye11
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.
 
Physics news on Phys.org
  • #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.
 
  • #3
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?
 
  • #4
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
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.
 

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

1. How do you represent a graph with X={1,2,3,4} and G=(V,E)?

In this graph, the set X represents the vertices or nodes, which are the objects or elements being connected. The set G represents the edges, which are the connections or relationships between the vertices.

2. What is the purpose of exploring a graph?

Exploring a graph allows us to analyze and understand the relationships between the elements in a set. It can also help us identify patterns and trends, and make predictions based on the graph's structure.

3. How do you determine the number of vertices in a graph?

In this graph, the number of vertices is equal to the number of elements in the set X, which is 4. Therefore, there are 4 vertices in this graph.

4. Is this graph directed or undirected?

Without further information, it is impossible to determine if this graph is directed or undirected. A directed graph has edges with specific directions, while an undirected graph does not. Additional information is needed to determine the directionality of the edges in this graph.

5. Can you provide an example of how to explore a graph with this set and representation?

One way to explore this graph is to create a visual representation, such as a graph drawing, and label the vertices and edges. Then, you can analyze the connections between the vertices and identify any patterns or trends. For example, you may notice that all vertices are connected to each other, forming a complete graph.

Back
Top