Solving K Complete Graph: Edges & Vertices Ratio

In summary, the conversation discusses finding a formula for the number of edges in a complete graph Kn, as well as the ratio of edges to vertices as n increases. The suggested formula is n/2 * (n-1), but the ratio is still uncertain. The conversation also mentions using this formula as a rule of inference in a verbal argument, and finding a necessary relationship between the number of edges and vertices in a graph represented on a Torus. The concept of "ratio" is also clarified as being represented by x/y.
  • #1
chaotixmonjuish
287
0
I'm having problems taking a stab at this question:

Find a formula for the number of edges in Kn. What happens to the ratio of edges to verticies as n increases?

Formula: n/2 * (n-1)
Ratio: this is the part I can't figure out. I assumed the ration is n/(n/2*(n-1))

Give a brief verbal argument that employs this rule of inference?


Find a necessary relationship between the number of edges and number of vertices's of a graph G if it can be represented on a Torus?

The last two parts have completely stumped me.
 
Physics news on Phys.org
  • #2
Doesn't the ratio of [itex]x[/itex] to [itex]y[/itex] mean [itex]\frac{x}{y}[/itex]?
 

1. What is a K Complete Graph?

A K Complete Graph is a type of graph theory that contains a set of vertices connected by edges, where every vertex is connected to every other vertex. It is also known as a fully connected graph or a clique.

2. How do you determine the number of edges in a K Complete Graph?

The number of edges in a K Complete Graph can be determined by using the formula E = (V * (V-1)) / 2, where V is the number of vertices. This is because each vertex is connected to every other vertex, and the total number of possible connections is V * (V-1). However, since each edge is counted twice, we divide by 2 to get the final number of edges.

3. What is the ratio of edges to vertices in a K Complete Graph?

The ratio of edges to vertices in a K Complete Graph is always 1:1, meaning that the number of edges is equal to the number of vertices. This is because each vertex is connected to every other vertex, resulting in a fully connected graph.

4. How does the number of edges change as the number of vertices increases in a K Complete Graph?

As the number of vertices increases in a K Complete Graph, the number of edges also increases. This is because with each new vertex added, there are more possible connections to be made with the existing vertices, resulting in more edges.

5. Can a K Complete Graph have a different number of edges than the formula dictates?

No, the number of edges in a K Complete Graph is determined by the formula E = (V * (V-1)) / 2 and cannot be changed. This is because the definition of a K Complete Graph requires that each vertex is connected to every other vertex, resulting in a specific number of edges according to the formula.

Similar threads

MHB Prove the minimum and maximum edges in a graph
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
MHB Graph: showing that diameter is greater than average pairwise distance
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K
I Circuits or edge-disjoint unions of circuits in a connected graph
    • Topology and Analysis
Replies
1
Views
788
MHB Show that HSC is NP-complete
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
I The number of intersection graphs of ##n## convex sets in the plane
    • General Math
Replies
2
Views
691
I Euler's Formula for planar graphs - 1 or 2 ?
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
947
MHB 5 Vertices Denoted by K5 part B
    • Set Theory, Logic, Probability, Statistics
Replies
26
Views
11K
I Edge connectivity of a graph given the number of edge disjoint paths
    • General Math
Replies
1
Views
1K
MHB Understanding Two Graph Theory Problems
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
MHB Graph theory proof related to trees
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top