Proof: Connected Graph of Order n Has at least n-1 Edges | Graph Theory

A connected graph of order n has at least n-1 edges, in other words - tree graphs are the minimally connected graphs. We'll be proving this result in today's graph theory lesson!

We'll be using a special type of contradiction proof called a proof by minimum counterexample. If we assume that there is a graph contradicting our claim, we can consider one such graph of minimum order, then we will show that this "minimum order counterexample" is actually not a minimum order counterexample, producing a contradiction and proving our claim.

Connected graphs with one less edge than vertices NEVER have cycles, and connected graphs with no cycles are called tree graphs; check out these lesson on them...

I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

Follow Wrath of Math on...

[tifawine]

BUT the triangel has 3 sides. Why should be just 2 edges?

[tchappyha]

Thank you very much for your elegant proof.
The following exercise is B.4-3 on p.1173 in "Introduction to Algorithms 3rd Edition" by CLRS:
Show that any connected, undirected graph G = (V, E) satisfies |E| >= |V| - 1.

[PunmasterSTP]

Minimal counterexample? More like "Magnificent lectures, with quality that's more than ample!"

[-Manasa-ijbb]

Consider an undirected graph G that has n distinct vertices where each vertex has degree 2. Assume n≥3. What is the maximum number of circuits that G can contain? If all the vertices of G are contained in a single circuit, what is the maximum number of vertices that can be contained in an independent set?

[LearningCS-jpcb]

Didn't get the minimum order part of proof, but luckily i can understand alternate contradiction using same argument.
once we reduce proving G is counter example G-v as counter example, we can keep using same argument (of there must exist end vertex ) repeatedly and end up with G-{v1, v2, v3, ...vn} which is size 3. There is no size 3 counter example graph, so our original graph of n is also not a counter example.
Thanks!

[rahulkhatav]

Good explanation. Hope it saves me for the exams 😅

[abhistyadav]

How do you prove that after removing an end vertex the graph still remains connected

[eddieadnan]

Hello can you make a vdieo on Prufer code

[parasmittal]

Great proof, thanks a lot for this !!

[monke]

Really appreciate your videos.

Before watching this video, i tried to prove this statement on my own. Here goes my attempt:


Let G be connected graph. If G has no cycles, then it is a tree and the statement follows immediately from one of the alternative definitions for a tree. Otherwise, if G has a cycle, deleting an edge from that cycle lowers the number of edges and leaves a connected graph G_1. Since G has finitely many cycles, we can iteratively construct a sequence of connected subgraphs G_j, G_j contained in G_{j-1}, j=0, ...k, with G_0=G, in such a way that one edge from a remaining cycle in G is removed at each step. Eventually we reach a tree, and then we notice that G has more edges than G_j, and this is exactly the result we want to prove, since G_k has V(G)-1 edges (because it's a tree).

Do you see any problem with this approach? Thanks in advance.

[kanikasihag]

Hey!!could you pls make a video on the que:
Let G be a connected graph with n vertices. Then prove that G is a tree iff every edge G is a bridge.plsss
I got this que. In one of my test and till then i am searching for the ans.😅😅😅

[dogkansarac]

dont you think using induction is way easier than this proof?