Graph Theory - connection proof

Click For Summary

Homework Help Overview

The problem involves proving that a graph with more than (n-1)(n-2)/2 edges is connected. The subject area is graph theory, specifically focusing on the properties of connected graphs and edge counts.

Discussion Character

  • Exploratory, Assumption checking

Approaches and Questions Raised

  • Participants discuss the initial attempts to visualize the problem through examples and tables, noting a pattern of connectivity with the given edge count. Questions arise regarding the definitions of "connected" and the meaning of n in this context.

Discussion Status

The discussion is ongoing, with participants exploring different approaches, including the suggestion to consider a proof by contradiction. Some guidance has been offered regarding the construction of disconnected graphs to illustrate edge limits.

Contextual Notes

There is a lack of clarity regarding the definitions and constraints of the problem, particularly what constitutes a "connected" graph and the implications of the edge count in relation to graph connectivity.

oneamp
Messages
222
Reaction score
0

Homework Statement



Prove that if a graph has > (n-1)(n-2) /2 edges, it is connected.

Homework Equations



??

The Attempt at a Solution



I've drawn several examples and made tables, and I can see that the graph is indeed connected if it has more edges than [(n-1)(n-2)]/2. But what I cannot do so far is prove it. How can I start doing this proof?

Thanks
 
Physics news on Phys.org
oneamp said:

Homework Statement



Prove that if a graph has > (n-1)(n-2) /2 edges, it is connected.

Homework Equations



??

The Attempt at a Solution



I've drawn several examples and made tables, and I can see that the graph is indeed connected if it has more edges than [(n-1)(n-2)]/2. But what I cannot do so far is prove it. How can I start doing this proof?

Thanks

What does n represent here?
How does your book define "connected" graph?
 
n is the number of vertices. Connected graph means that there is no vertex that is not connected to any other by some path. Also the graph is undirected and simple (simple meaning no loops, no more than one edge between any two vertexes.)
 
You might want to do the opposite proof: if a graph is disconnected, it has fewer than or equal to (n-1)(n-2)/2 edges.

In particular it shouldn't be hard to construct the disconnected graph with the most edges.
 
That helped, thank you.
 

Similar threads

Prove that there exists a graph with these points such that....
  • · Replies 2 ·
Replies
2
Views
2K
Strong Induction, Tangled Graph
  • · Replies 3 ·
Replies
3
Views
3K
Person i belongs to a clique iff ith diagonal entry of B^3 is positive
  • · Replies 9 ·
Replies
9
Views
2K
Prove the decomposition of a graph w/ even edges produce a 2-path set
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Circuits or edge-disjoint unions of circuits in a connected graph
  • · Replies 1 ·
Replies
1
Views
3K
Euler circuit in a directed multigraph
  • · Replies 2 ·
Replies
2
Views
5K
How to construct a graph with girth = twice the diameter + 1
  • · Replies 2 ·
Replies
2
Views
2K
Do these two statements imply an underlying induction proof?
  • · Replies 7 ·
Replies
7
Views
1K
Spectral Graph Clustering: where does the 'scoring' function come from
  • · Replies 1 ·
Replies
1
Views
2K
Proving Cut Vertices in Simple Graphs
  • · Replies 2 ·
Replies
2
Views
2K