Graph Theory Help: Finding # of Graphs w/ n Vertices & k Edges

In summary, the total number of distinct graphs with the set of vertices V={1,2,...,n} and k edges can be found by choosing k pairs of vertices from the total of (n^2 - n)/2 pairs. For directed graphs, this number would be multiplied by 2, and for graphs with loops, the total number would be based on 1/2 n^2 instead of 1/2 n(n-1).
  • #1
erogol
14
0
The graph theory HELP!

How many distinct graphs can be found by the set V={1,2,...,n} with k edges?

For this question i conclude that totao.l number of distinct graphs comes with 2^(choose two in n)

but i cannot find the solution which gives the relation with k edges can you help me?
 
Physics news on Phys.org
  • #2


There are a total of (n^2 - n)/2 = 1/2 n(n-1) pairs of vertices. You pick k out of these, so you have Comb(1/2 n(n-1), k) possibilities.

If you're talking about directed graphs, multiply this by 2. If you allow for loops, take 1/2 n^2 instead of 1/2 n(n-1).
 

1. How do I find the number of graphs with a certain number of vertices and edges?

To find the number of graphs with a specific number of vertices and edges, you can use the formula n^(n-1)/2, where n is the number of vertices. This formula is known as the number of labeled graphs with n vertices. However, if you are looking for the number of unlabeled graphs, you can use the formula 2^(n(n-1)/2)/n!, where n is the number of vertices.

2. Can I use any graph to represent a problem in graph theory?

Yes, you can use any graph to represent a problem in graph theory as long as it follows the basic rules of a graph. This includes having vertices and edges, and the edges connecting two vertices without any overlapping or crossing.

3. What is the significance of the number of edges in a graph?

The number of edges in a graph is significant as it can affect the connectivity and complexity of the graph. For example, a graph with a large number of edges may have a higher level of connectivity, making it more difficult to solve problems related to that graph.

4. How do I know if a graph is connected or not?

A graph is considered connected if there is a path between any two vertices in the graph. To determine if a graph is connected, you can use graph algorithms such as depth-first search or breadth-first search. These algorithms will help you identify if there is a path between two vertices or not.

5. Can I use graph theory to solve real-world problems?

Yes, graph theory can be applied to various real-world problems, including network optimization, transportation planning, and social network analysis. It is a powerful tool for visualizing and analyzing complex relationships and can provide insights and solutions to real-world problems.

Similar threads

A Concrete examples of randomness in math vs. probability theory
    • Set Theory, Logic, Probability, Statistics
Replies
11
Views
476
MHB Minimum Degree of a Random Graph (Probabilistic Method)
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
I Circuits or edge-disjoint unions of circuits in a connected graph
    • Topology and Analysis
Replies
1
Views
782
MHB How many edges does the graph have?
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
MHB How many new branches will the complement graph of a deleted edge have?
    • Set Theory, Logic, Probability, Statistics
Replies
11
Views
2K
I The number of intersection graphs of ##n## convex sets in the plane
    • General Math
Replies
2
Views
681
MHB Graph Grammer Function For Two Exotic Graphs Question please.
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
MHB Finding a Minimal Vertex Cover & Max Sets for a Graph
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
I When does ## { n \choose k } ## represent set of lists?
    • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
I Find Smallest Subtree of G w/ Nodes from S
    • General Math
Replies
5
Views
1K

Hot Threads

Recent Insights

Back
Top