Graph theoretical problems

  • Thread starter nuuskur
  • Start date
  • #1
704
513

Homework Statement


#1 Does there exist a graph that has m times more edges than vertices?
#2 How to calculate the number of possible graphs given the number of vertices and edges? Connected graphs, disconnected graphs.

Homework Equations




The Attempt at a Solution


#1We know that a complete graph has [itex]\frac{n(n-1)}{2}[/itex] number of edges, n being the number of vertices in the complete graph. Hence [itex] m = \frac{n-1}{2} \Leftrightarrow n = 2m + 1[/itex].

How to approach this problem if one has no knowledge of complete graphs having [itex]\frac{n(n-1)}{2}[/itex] edges?
-------
#2 A connected graph is such a graph whose every 2 vertices can be connected via a path.
If we have, say, 5 vertices and 7 edges.

Well, from the complete graph we know there are total of [itex]\frac{n(n-1)}{2}[/itex] edges and we have to use 7.
It would be 10 choose 7 graphs - but are they all connected?
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
37,988
7,702
How to approach this problem if one has no knowledge of complete graphs having n(n−1)/2 edges?
It's not something you need prior knowledge of. You only need to find one example. If you start in the obvious way, looking for an example in which every vertex has r edges, it is easy to see that r =2m and should be apparent that a graph of r+1 vertices all interconnected is an example.
How to calculate the number of possible graphs given the number of vertices and edges?
That's a very hard problem, unless you are supposed to regard the vertices as distinct. In which case, the question would have been better worded as the number of graphs with m edges that can be formed on n labelled vertices.
Connected graphs, disconnected graphs.
Not sure what this clause means. Does it mean counting those cases separately or counting them all together? You have interpreted it as separately, so I'll assume that's right.
Clearly they aren't necessarily all connected in general. For 5 vertices and 7 edges, they will all be connected. (Suppose such a graph is not connected, falling into k and n-k vertex sets. What's the maximum number of edges?) But for 4 to 6 edges on 5 vertices there can be both connected and disconnected graphs.
Sounds like an application of inclusion-exclusion.
 

Related Threads on Graph theoretical problems

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
15
Views
7K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
692
Replies
18
Views
2K
  • Last Post
Replies
1
Views
1K
Top