Category Archives: Graph Theory

After discussing connectivity and edge-connectivity, I want to present a theorem that gives us a different prespecive about those terms. To do so, I will present and prove Menger’s theorem, this theorem will help us deduce some great conclusions about connectivity! Before I’ll present the theorem though, I want to define a new term –Continue reading “Menger’s theorem”

In the last post I’ve presented the term of Connectivity, vertex-cut and cut-vertices. I also mentioned that we can disconnect a graph with edges. So that what I am going to talk about here – The term of Edge Connectivity. Some new definitions Suppose that is a graph. A set of edges is said toContinue reading “Edge Connectivity”

How can we disconnect a graph? Is there a ‘good’ way to do so? How hard we need to work in order to disconnect a graph? Are there graphs that are ‘more’ connected than others? Well, let’s start answering those questions. the easiest is the first. Of course we can disconnect a graph! There areContinue reading “Connectivity”

In the last post we’ve seen that the number of spanning trees in the complete graph is . That’s a great result, however, I am not satisfied yet… So we know how many spanning trees has – big deal! Why restrict ourseleves only to ? wouldn’t it be better to find the number of spanningContinue reading “Kirchhoff’s theorem”

In the last post I’ve introduced the term of trees and proved a theorem that allows us to fully understand trees. They are connected, they have edges (where is the number of vertices) and they have no cycles. I’ve also presented the term of a spanning sub-graph – which is a sub-graph of a graphContinue reading “Cayley’s formula”

After we’ve seen in the last post an elegant example for using graph to solve a problem, it’s now time to proceed and meet some more definitions. In math, when we are dealing with a structure, we usually like to define a sub-structure, examples for that are: sub-set, sub-group, sub-vector space and so on. TheContinue reading “Sub-Graphs and Trees”

So after the introduction, it is now time to dive in to the theory itself. First, I am warning you, in this post I am going to present a lot of definitions, and I mean it, there will be a lot of it. However, this post is crucial in order to understand later posts, andContinue reading “Graph Theory – setting the ground”