Combinatorics planar graph dealing with triples

In summary, A complete tripartite K r,s,t is a generalization of a complete bipartite graph. It consists of three subsets of vertices, with each vertex in one subset being adjacent to all vertices in the other two subsets. The graph is planar if and only if the sum of the subsets is less than or equal to 6. The possible triples for r,s,t are (3,3,0), (3,2,1), (2,2,2), (2,1,3), and (1,1,4).
  • #1
dugga boy
4
0
A complete tripartite K r,s,t is a generalization of a complete bipartite graph. There are three subsets of vertices, r in teh first subset, s in the second subset, and t in the third subset. Every vertex in one particular subset is adjacent to every vertex in the other two subsets; that is, a vertex is adjacent to all vertices except those in its own subset. Determine all the triples r,s,t for which K r,s,t is planar.


I am thinking that there must be a minium of 12 vertices...But I am not sure...



. .
. .
. .
. . Maybe two side by side and one underneath? I am not sure

. . . .
 
Physics news on Phys.org
  • #2
A complete tripartite K r,s,t is planar if and only if r + s + t ≤ 6. So, the valid triples are (3,3,0), (3,2,1), (2,2,2), (2,1,3), and (1,1,4).
 

1. What is combinatorics and how does it relate to planar graph dealing with triples?

Combinatorics is a branch of mathematics that deals with counting and arranging objects. In the context of planar graphs, combinatorics can be used to determine the number of ways to arrange vertices and edges in a specific pattern or configuration.

2. What is a planar graph and how is it different from other types of graphs?

A planar graph is a type of graph where the edges do not cross each other when drawn on a plane. This means that the graph can be represented without any overlapping lines or edges. Other types of graphs, such as non-planar graphs, can have edges that intersect.

3. What are triples in the context of combinatorics planar graphs?

In combinatorics planar graphs, triples refer to a specific type of arrangement of vertices and edges. A triple consists of three vertices connected by three edges, forming a triangular shape. The study of triples is important in understanding the overall structure and properties of planar graphs.

4. How is combinatorics planar graph dealing with triples applied in real-life situations?

Combinatorics planar graph dealing with triples has various applications in real-life situations, such as in network design, scheduling, and resource allocation problems. It is also used in computer science for data structure and algorithm design, as well as in physics and chemistry for modeling molecular structures.

5. Are there any limitations to using combinatorics in analyzing planar graphs with triples?

While combinatorics can be a powerful tool in understanding and analyzing planar graphs with triples, there are some limitations. In particular, as the number of vertices and edges in a graph increases, it becomes increasingly difficult to use combinatorial methods to analyze it. In these cases, more advanced mathematical and computational techniques may be necessary.

Similar threads

Hall's theorem problem (graph theory)
    • Calculus and Beyond Homework Help
Replies
12
Views
3K
Proving uniqueness of almost irregular graphs with equal degrees for n=2k
    • Calculus and Beyond Homework Help
Replies
3
Views
2K
B 4-colours theorem can be proved visually
    • General Math
Replies
21
Views
1K
I Finding the dependence of maximum vertex degree on k-colorability
    • General Math
Replies
1
Views
1K
Combinatorics: Steiner Triple System
    • Calculus and Beyond Homework Help
Replies
7
Views
959
B Open sets in quotient topology
    • Topology and Analysis
Replies
8
Views
2K
Combinatorics -- Counting Sets of Binary Strings
    • Calculus and Beyond Homework Help
Replies
3
Views
2K
Graph Theory - bipartite related proof
    • Calculus and Beyond Homework Help
Replies
4
Views
7K
I When does ## { n \choose k } ## represent set of lists?
    • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
MHB Probability of Having a Totally Dominating Set (Probabilistic Methods)
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top