Graph theoretical problems

In summary, the conversation discusses the possibility of a graph having a certain number of edges compared to vertices, and how to calculate the number of possible graphs given a certain number of vertices and edges, including connected and disconnected graphs. This can be approached by starting with a complete graph and finding one example, and potentially using inclusion-exclusion to account for different types of graphs.
  • #1


Science Advisor

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?
Physics news on
  • #2
nuuskur said:
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.
nuuskur said:
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.
nuuskur said:
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.

1. What is graph theory?

Graph theory is a branch of mathematics that studies the properties and relationships of graphs, which are mathematical structures used to model pairwise relations between objects.

2. What are some real-world applications of graph theory?

Graph theory has many practical applications, including social network analysis, transportation and logistics planning, computer networking, and circuit design.

3. How are graphs represented in graph theory?

Graphs are typically represented using a set of vertices or nodes, connected by edges or arcs. They can also be represented as matrices or adjacency lists.

4. What are some common types of graphs in graph theory?

Some common types of graphs include directed and undirected graphs, weighted and unweighted graphs, complete graphs, and bipartite graphs.

5. What are some algorithms used in graph theory?

There are many algorithms used in graph theory, including depth-first search, breadth-first search, Dijkstra's algorithm, and Prim's algorithm. These algorithms are used to solve various graph theoretical problems, such as finding shortest paths and detecting cycles in graphs.

Suggested for: Graph theoretical problems