Articles of graph theory

Oriented graph VS directed graph?

Alright, while the definitions are stated in my lecure notes, textbooks and wiki, I’ll be honest, it just explodes my mind with what seems like word sorcery. Definition A directed graph is called an oriented graph if it is the orientation of an undirected graph. What are the distinctions between Oriented graphs and digraphs? An […]

Finding an MST among all spanning trees with maximum of white edges

Let an undirected graph $G=(V,E)$ with the color property $c(e)$ for every edge (could be black or white) and a weight property $1 \le w(e) \le 100$. Find the MST from the set of all spanning trees with the maximum number of white edges. Do it in linear time ($O(|V|+|E|$). So basically I want to […]

Enumerate out-trees that include a set of nodes in a directed graph

Given a digraph A, and an N set of nodes in the digraph. I need to enumerate the set of out-trees that contain those nodes. Where all the the out-trees leaves terminate on a node in set N. EDIT: I am now exploring options other than the one below. Also in my particular domain I […]

Number of possible graphs from a reachability matrix?

I need to know how to work out how many possible different digraphs can be drawn from a given reachability matrix. It needs to be with the minimum number of arcs between the nodes within the graph (which i believe is 10 for the one given). If someone could explain it step by step for […]

$K_n$ as an union of bipartite graphs

Theorem: The complete graph $K_n$ can be expressed as the union of $k$ bipartite graphs if and only if $n \leq 2^k.$ I would appreciate a pedagogical explanation of the theorem. Graph Theory by West gives the proof but I don’t understand it. Also this referece has the proof, but it kills me with the […]

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we’re given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise disjoint. I’m wondering how we can show 3-dimensional matching $\le_p$ exact cover. Given an instance of the 3-dimensional […]

Analogue of Fáry's theorem taking sphere and geodesics instead of plane and straight lines.

Fary’s theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments (see Wikipedia). The proof is based on the Art gallery theorem, so I would have asked also this latter. But, perhaps there is a simpler answer on my question. In any case, my question […]

Numbers of ways $k – 1$ edges to be added to $k$ connected components to make the graph connected

Given a graph $G$ with $n$ vertices and $m$ edges. Let us say it has $k$ connected components. Find out how many numbers of ways you can add $k – 1$ edges to make the graph connected. Is it any standard graph problem? How can it be solved?

Graph Proof by induction.

Can you prove via induction that there exists a node in a directed graph of n nodes that can be reached in at most two edges from every other node in the graph. Every node in the graph is required to have an edge with every other node that either points out or in (For […]

How can I prove that $\left|\sum_{i=0}^r (-1)^i \binom{a}{i} \binom{n-a}{r-i}\right| \leq \binom{n}{r}$?

This is a conjecture: How can I prove that \begin{equation} \left|\sum_{i=0}^r (-1)^i \binom{a}{i} \binom{n-a}{r-i}\right| \leq \binom{n}{r} \end{equation} for $0\leq a \leq n$, $0\leq r \leq n$ and $n,r,a \in \mathbb{N}$ ?