Intro to Tree Graphs | Trees in Graph Theory, Equivalent Definitions

What are trees in graph theory? Tree graphs are connected graphs with no cycles. We'll introduce them and some equivalent definitions, with of course examples of tree graphs in today's graph theory video lesson!
Some equivalent definitions of tree graphs are as follows.
A graph is a tree if and only if it is connected and it has one less edge than it has vertices (its size is one less than its order).
A graph is a tree if and only if every pair of distinct vertices is connected by exactly one path.
If every component of a graph is a tree, then it is called a forest!
A vertex of degree one in a tree is called a leaf.
SOLUTION TO PRACTICE PROBLEM:
We want to prove that a connected graph has no cycles if and only if each pair of its vertices is connected by exactly one unique path. I won't detail a full proof here, as we will go over it in a lesson soon. The idea is as follows.
Let G be connected and have no cycles. Suppose for the sake of contradiction that there exists a pair of vertices, u and v, that are connected by two distinct paths P1 and P2. It can be shown that two particular subpaths of P1 and P2 form a cycle, producing a contradiction. You just need to figure how to construct those subpaths to produce a cycle.
Let G be a graph where each pair of vertices is connected by exactly one unique path. Suppose for the sake of contradiction that G contains a cycle C. Let u and v be adjacent vertices in the cycle. Then (u, v) is a u-v path and the u-v path in C not containing the edge uv is a different u-v path. This is a contradiction.
I hope you find this video helpful, and be sure to ask any questions down in the comments!
********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.
Vallow Bandcamp: vallow.bandcam...
Vallow Spotify: open.spotify.c...
Vallow SoundCloud: / benwatts-3
********************************************************************
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic