Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions! th-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin Graph Theory course: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html Graph Theory exercises: th-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
Hello Professor, thank you for all your videos. I just subscribed. How can I prove that a directed graph that have one and only one circuit, where all the vertices have an out degree equal to one is connected? Thanks in advance
Thanks Theophile! I would do this by contradiction. Suppose our graph G is not connected, then it has two components, G1 and G2, where at least one of them doesn't have a circuit (since the graph has only one circuit). Say G1 doesn't have a circuit and take a vertex v1 from G1. Since v1 has outdegree 1, it is adjacent to another vertex in G1, say v2. We can proceed in this manner establishing adjacencies to new vertices vi and since we're discussing finite graphs there are only two possibilities: 1) at some point a vi is adjacent to a previous vertex in the graph, thus creating a circuit, which is a contradiction, or 2) at some point vi is not adjacent to any other vertex, and thus has outdegree 0, again a contradiction.
Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!
th-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
Graph Theory course: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Graph Theory exercises: th-cam.com/play/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L.html
Great video, very good explanation with simple examples. thanks!!!
Thanks for watching!
This video was diameterrific! 👍
Oh, wow! Your face is so bright! (Both in terms of luminosity and in terms of excitement!) 😀😀😀
The video was great. You didn't mention that distance means actually ‘minimum distance’. Great job, though! ❤ (Subscribed 😇)
Thank you!!
My pleasure!
\sum_{uv\in E(G)}deg_{G}(u) how to calculate this professor
Hello Professor, thank you for all your videos. I just subscribed. How can I prove that a directed graph that have one and only one circuit, where all the vertices have an out degree equal to one is connected?
Thanks in advance
Thanks Theophile! I would do this by contradiction. Suppose our graph G is not connected, then it has two components, G1 and G2, where at least one of them doesn't have a circuit (since the graph has only one circuit). Say G1 doesn't have a circuit and take a vertex v1 from G1. Since v1 has outdegree 1, it is adjacent to another vertex in G1, say v2. We can proceed in this manner establishing adjacencies to new vertices vi and since we're discussing finite graphs there are only two possibilities: 1) at some point a vi is adjacent to a previous vertex in the graph, thus creating a circuit, which is a contradiction, or 2) at some point vi is not adjacent to any other vertex, and thus has outdegree 0, again a contradiction.
@@WrathofMath Will the same apply to a countable graph also? I am pretty sure it will