Graph Theory - connection proof

  • Thread starter oneamp
  • Start date
  • #1
oneamp
219
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
 

Answers and Replies

  • #2
36,311
8,281

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?
 
  • #3
oneamp
219
0
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.)
 
  • #4
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
2021 Award
5,216
1,168
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.
 
  • #5
oneamp
219
0
That helped, thank you.
 

Suggested for: Graph Theory - connection proof

Replies
7
Views
358
Replies
12
Views
340
Replies
2
Views
303
Replies
2
Views
295
Replies
2
Views
206
  • Last Post
Replies
4
Views
152
  • Last Post
Replies
6
Views
830
Replies
17
Views
377
Top