Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

7
votes
1answer
351 views

Graph theory problem (edge-disjoint matchings)

Find the smallest number $x$ so that if an $n$-vertex simple graph has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings* ($k$ is a positive integer, $n$ is an even ...
0
votes
1answer
40 views

3-regular planar graph

Yet another question I was going over and struggled. Given a 3-regular connected planar graph, so that every vertex lies on the edge of a face of length 4, of a face of length 6 and of a face of ...
5
votes
1answer
88 views

What is the name of a graph made of k copies of a 4-cycle connected end to end in a chain, possibly with leaves?

Do graphs of the following sort have a specific name? We've been calling them Cactapillars, as they're cacti that look a little like caterpillars (and the name Caterpillar already refers to a ...
7
votes
3answers
257 views

Probability that a vertex in the spanning tree of an $N$ x $N$ grid graph is a leaf

Suppose we have an $N$ x $N$ grid graph $G(V,E)$ and we construct a spanning tree of this graph in the following way. Start with a set $S$ which contains only the vertex at the top left corner of the ...
0
votes
1answer
26 views

Distinguishing between two sets of tournament partition

A "tournament" is a complete graph such that each edge is directed one way or the other (but not both). Does there exist a tournament of size $2n$ such that we can partition it into two sets $A,B$, ...
2
votes
2answers
284 views

Shortest path in linear time

Suppose each edge can receive one of two weights $\{r_1,r_2\}$ where $r_1$ and $r_2$ are real and non-negative. And suppose $r_1 \leq r_2$. How do you find the shortest path from a given vertex s to ...
1
vote
1answer
23 views

Name for a generalized relation to be a multiset?

A relation between two sets $A$ and $B$ is a subset of $A \times B$. If taking a multiset subset of $A \times B$, e.g. allowing $(a,b)$ appears twice in the subset, is there a name for such a ...
0
votes
1answer
18 views

What are the rules for plotting directed graphs?

Say I have an ordered pair of sets. One contains the vertices and the other - edges. What are the rules for actually plotting the graphs with these givens? Can a graph be plotted differently given ...
1
vote
3answers
67 views

Does a path can be Hamiltonian and Eulerian at the same time?

If so does it force it to be a simple circle? Or any other restrictions? How would it look like? Thanks in advance
2
votes
2answers
23 views

Is there a name for this type of graphs?

From a graph G I want to construct a graph (lets call it) G# with the following properties: Each node and each edge of G is a node of G# For each e in G connecting the nodes n1, n2 there exist the ...
0
votes
0answers
34 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
2
votes
0answers
15 views

Sampling from a graph

Suppose you have a graph $G=(V,E)$ that is unobservable globally and you wish to take a sample from the vertices of that graph to infer something about its global properties from local properties. ...
0
votes
1answer
25 views

Proving any N x M undirected two dimensional grid is bipartite

I am trying to self learn graph theory basics by myself, and it would be really helpful is somebody could double check one of my answers: Let $N$ and $M$ be positive integers. Show that any $N$ x ...
0
votes
0answers
18 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
0
votes
0answers
9 views

Average time to split a square lattice under random edge deletions

Suppose one successively deletes uniform at random edges from the square lattice with periodic boundary conditions and $L\times L$ sites. How many steps, in average, are necessary to create a second ...
2
votes
3answers
33 views

Prove that if a $k$-regular bipartite graph has a bipartition $(x,y)$ then $\vert x\vert=\vert y \vert$

A problem I don't know how to attack... a bipartite is supposed to have one end in $x$ and one in $y$. A graph is $k$-regular if $d(v)=k$ for all $v\in v(G)$
2
votes
0answers
28 views

Is there a bound for the genus of the generalized petersen graphs?

I've looked online and could only find a bound for specific generalized petersen graphs. Does any bound (lower or upper) depending on $n$ and $k$, where $n$ is the order of a cycle and $k$ is the ...
1
vote
2answers
49 views

Prove that a complement graph of a tree is either connected or it's a union of an isolated vertex and a full graph

I managed to prove the second part - that a tree that is one vertex with n-1 degree and all the rest are connected to it - the complement graph of such tree is an isolated vertex and the rest of the ...
3
votes
0answers
64 views

A game on a smaller graph

In this question Alice and Bob play a game on $K_{2014}$, Alice directing one edge, Bob directing $1$ to $1000$ edges with Alice trying to make a cycle. The proof that Alice can win depended on the ...
0
votes
1answer
62 views

Convergence of $\text{ex} (n;P)/ \binom n2$ for Petersen graph

This question is linked to For a graph $G$, why should one expect the ratio $\text{ex} (n;G)/ \binom n2$ to converge? where an argument was given that this specific ratio converges for ...
0
votes
1answer
40 views

Proof that a graph is 5-colorable

So I had an exam today and one of the questions were: G is an undirected graph, and every two of its odd-lengthed cycles have a common vertex. Prove that G is 5-colorable. So I found this answer ...
0
votes
1answer
30 views

I need to understand bipartite graphs

Hi i didnt find good information on the web about bipartite graps. For example does the sum of the degrees on both sides have to be equal? or a bipartite graph G (with side A & B) whose number of ...
0
votes
0answers
25 views

Is it allowed to draw multiple loops in not simple graph?

I mean multiple loops on the same node for example can I have a graph whose degree level is 6 and it contains only one node?
0
votes
1answer
25 views

No minimal imperfect graph of order 200

Prove that there is no minimal imperfect graph of order 200, without using the Strong Perfect Graph Theorem.
2
votes
1answer
30 views

Thickness of $K_{5,5}$

How to compute the thickness of $K_{5,5}$? By Euler formula it is greater than 1, and 3 is constructible($K_{2,5}*3$), but how to prove it is not 2?
2
votes
1answer
39 views

What is the realization of a graph in $\mathbb{R}^d$?

I am an undergraduate who has been overhearing students talking about realizations of graphs in $\mathbb{R}^d$, and I am curious to know what that means. To be honest, I don't even know what a ...
0
votes
0answers
30 views

A planar graph has either 2 faces or 2 vertices of degree less than 3

Practicing for an upcoming test, I stumbled upon this question: A planar graph with at least three vertices has either 2 faces of length at most 3, or 2 vertices of degree at most 3. Which is a ...
3
votes
0answers
34 views

An undirected graph $G$ can be decomposed into simple edge-disjoint cycles if and only if all of its vertices have even degree.

Research effort: $\rightarrow)$ I think this is relatively easy. $\leftarrow)$ Let $G = (V,E)$, let $w$ be any vertex of $G$, given that all the vertex have even degree, I'm assured that I can ...
15
votes
2answers
233 views

A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
2
votes
2answers
31 views

How many spanning trees (undirected) are there with exactly k leaf?

It occurred to me that in order to find how many of those are there, for every $k$ it's a bit different way of thinking, for example: for $k$ = 3 the answer is: $\binom{n}{3}(n-3)\frac{(n-2)!}{2!}$ ...
0
votes
1answer
26 views

Constructing an eigenvector for a certain matrix representing a graph with a perfect code

Let $A$ be a symmetric $(0,1)$-matrix whose row sum is $r.$ Suppose I have a $(0,1)$ vector $v$ such that $$Av = \vec{1} - v.$$ By taking the vector $$u = \vec{1} - (r+1)v$$ we see that $$Au = A ...
0
votes
0answers
32 views

Smart Travelling Agent Problem

Smart travel agent, Mr. X's is to show a group of tourists a distant city. As in all countries, certain pairs of cities are connected by two-way roads. Each pair of neighboring cities has a bus ...
2
votes
1answer
47 views

Number of paths from A to B with no direction constraints

There's a fairly common problem finding paths which is usually stated something like this: Consider a grid that is 4 rows by 4 columns with the upper left corner named A and lower right corner ...
0
votes
0answers
12 views

compare magnitude of elements of Perron-Frobenious vector

Consider a nonnegative, primitive matrix $A=(a_{ij})_{n\times n}$ with positive diagonals. From the Perron-Frobenious theorem, the spectral radius $\rho(A)$ is an eigenvalue of $A$ and we have a ...
0
votes
1answer
66 views

Counting nodes in a random tree

Suppose we have a random tree where the probability that a node has $n$ successors is given by $\delta(n)$. What is the distribution of the number of nodes at the $s$-th level deep in the tree, ...
1
vote
1answer
33 views

Number of “Unique effective” paths on a grid.

I know that for an NxM grid there are "M+N choose N" unique paths to "opposite" {corner to corner} vertices. I would like to know how many "effective unique paths" there are if I discount for ...
0
votes
0answers
49 views

how to calculate the minimum edge cut set number of a graph

Given a graph, there are several kinds of minimum edge cuts. How to calculate how many cuts in the minimum edge cut set? Is there any algorithm solving this problem? Thank you!
0
votes
1answer
66 views

Cutting a chessboard into domino pieces!

A friend of mine gave me this problem from a european olympiad: Suppose we have a $8\times8$ chessboard. Each edge has a number; the number of ways of dividing this chessboard into $1\times2$ and ...
0
votes
0answers
37 views

What is exactly a DFS tree?

Here's a question: Claim: Every time we run the DFS algorithm on the following graph, The DFS tree will be lanyard (?) True \ False, Explanation: I Googled but I'm not pretty ...
0
votes
1answer
27 views

How many triangles are see in complete K5 graph

How many triangles are on picture below? On yahoo answers I have found that numbers of triangles in complete graph with n nodes is: $\frac{n(n-1)(n-2)}{6}$ But how this formula has been estimated? ...
0
votes
1answer
24 views

Find Maximum-Matching in a tree $T(V, E)$ in $O(V)$

It's a question from a previous exam that I'm trying to solve with no success. Suggest a Dynamic-Programming algorithm for the following problem: Input: indirected tree $T(V, E)$. ...
1
vote
0answers
67 views

Reiman theorem in extremal graph theory

I need a source where I can find a proof of the Reiman's thorem: If the graph G is quadrilateral($C_4$)-free, then $$|E(G)| \leq \frac{|V(G)|}{4}(1 + \sqrt{4\cdot|V(G)| - 3})$$ Here is the idea of ...
2
votes
1answer
50 views

Graph theoretic view on manifold triangulations

To make the question (hopefully) clearer, I reformulated it: Some triangulation $T$ of a smooth manifold $M$ is a piecewise linear manifold, because smooth manifolds are topological manifolds. Such a ...
1
vote
0answers
13 views

about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...
1
vote
0answers
24 views

When counting faces in a planar graph - when is each edge counted twice?

So I'm confused even though this is supposed to be simple: From what I understand, in a planar graph, if we count the edges of each face, we should get $\sum F_t \le 2|E|$ because an edge can ...
2
votes
1answer
58 views

Some questions on matroid

I have an unknown questions as follows. Thank you in advance. Let $M=(E,I)$ be a matroid and let $B$ and $B′$ be two disjoint bases of $M$. Let $B$ be partitioned into sets $Y_1$ and $Y_2$. Show ...
2
votes
0answers
77 views

Building Minimum warehouses

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. ...
0
votes
0answers
17 views

Induction over DAGs

I'd like to prove a proposition true over all valid Directed Acausal Graphs. I think I can do that by starting with a graph with one node and adding either a new node and connection, or a new valid ...
0
votes
1answer
30 views

Is Wikipedia incorrect about Eulerian tour?

Wikipedia's Eulerian Path states, An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single ...
1
vote
1answer
27 views

How many connected and undirected graphs are there when d(v) = 2 for every vertex in the graph.

Well, at the beginning I thought the answer would be (n-1)! But it's not correct. My assumption to that answer was that its just like putting n people in a circle, but it doesnt seem like its exactly ...