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”

# Category Archives: Graph Theory

## Edge Connectivity

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”

## 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”

## Kirchhoff’s theorem

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”

## Cayley’s formula

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”

## Sub-Graphs and Trees

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”

## Graph Theory – setting the ground

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”

## Graph Theory – Introduction

Intro & Intensions Hey everyone! I would like to welcome you to my very first post in this site. As you might read before at other locations at this site, I am going to discuss various topics in Mathematics, where one of them is going to be Graph Theory. For the section of Graph theory,Continue reading “Graph Theory – Introduction”