How to draw all subgraphs of K_5

  • Context: Graduate 
  • Thread starter Thread starter christodouloum
  • Start date Start date
Click For Summary
SUMMARY

This discussion focuses on the methodology for counting and drawing all trees of the complete graph K_5. The participant confirms that the total number of trees is 125, calculated using the formula 5^(5-2). They express difficulty in explicitly drawing these trees without duplication and mention a systematic approach involving the enumeration of graphs based on vertex valency. The participant identifies 14, 6, and 1 trees for 2-valent, 3-valent, and 4-valent vertices, respectively, indicating they are missing four trees. The conversation highlights the lack of a unified mathematical theory for subgraph enumeration in graph theory.

PREREQUISITES
  • Understanding of graph theory concepts, specifically complete graphs and trees.
  • Familiarity with combinatorial enumeration techniques.
  • Knowledge of vertex valency and its implications in graph structures.
  • Basic skills in algorithm design for graph enumeration.
NEXT STEPS
  • Research "Cayley's formula" for counting labeled trees in complete graphs.
  • Explore algorithms for "subgraph enumeration" in graph theory.
  • Study "graph isomorphism" to understand how to avoid duplicates in enumerations.
  • Learn about "graph drawing techniques" to visualize trees effectively.
USEFUL FOR

This discussion is beneficial for mathematicians, computer scientists, and anyone involved in graph theory, particularly those interested in combinatorial enumeration and algorithm development for graph structures.

christodouloum
Messages
35
Reaction score
0
Hi all. I have a simple question on methodology for counting graphs explicitely. I am trying to find all trees of the complete graph K_5. I know that the answer is 5^(5-2)=125 and that each should have only four of the ten edges. I am trying to understand how I would draw them down by hand explicitely. It turns out difficult to be sure that I have exactly all of them without replications etc.

My simple way at it was to search for 25 graphs that would not coincide when the vertices are "rotated" and try to find first the ones with up to two valent vertices, then up to 3-valent and then up to four-valent vertices (all of these times five). I found respectively 14,6 and 1 which means I am missing four. Does anyone know of a systematic way to do this?
 
Physics news on Phys.org
Your post raises (in my mind) the general question of how to specifically enumerate combinatorial possibilities in graph theory. I searched the web, expecting to find that this would be a well developed mathematical/programming subject. I don't see any unified mathematical theory of it. The biologists and chemists are interested in algorithms that accomplish the task and if you search for "subgraph enumeration", you find specialized algorithms.

You particular problem would be interesting to discuss. Currently, I don't know the algorithm for it.
 

Similar threads

MHB How Can a Random Number Table Be Used to Sample Cotton-Top Tamarins?
  • · Replies 1 ·
Replies
1
Views
1K
Graduate Cross section from subgraph in electron-proton DIS
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad What is the probability of drawing cards from a deck?
  • · Replies 6 ·
Replies
6
Views
3K
High School Probability in a dice game
  • · Replies 41 ·
2
Replies
41
Views
6K
Graduate Is there a stretching of the light curves of supernovae 1a?
  • · Replies 5 ·
Replies
5
Views
3K
MHB Understanding Sets, Relations, and Functions for Struggling Students
  • · Replies 1 ·
Replies
1
Views
2K
High School Which probability calculation is "more correct" in Baccarat games?
  • · Replies 9 ·
Replies
9
Views
6K
MHB What Are the Odds of All Canadian NHL Teams Missing the Playoffs?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Does K5 contain Eulerian circuits? (why?) If yes, draw them.
  • · Replies 4 ·
Replies
4
Views
8K
Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K