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

1
vote
0answers
45 views

How to sample the walk which visits each vertex of a graph specific number of times?

Is there any MCMC mathod that allow me to uniformly sample from all feasible walks where the following restrictions apply: ...
3
votes
1answer
365 views

Erdős-Rényi Random Graph Triangle Number

Let $G(n,p)$ be the usual Erdős-Rényi random graph. Let $T$ be the number of triangles in a realization of such a random graph. After counting $T$, let $T'$ be the number of triangles after selecting ...
3
votes
3answers
850 views

How many nodes are there in a 5-regular planar graph with diameter 2?

Undergrad here; I honestly have no idea what to do. I can't even imagine what a 5-regular graph with diameter 2 would look like, let alone a planar one.
0
votes
1answer
334 views

Spanning tree of a strongly connected directed graph.

Given a strongly connected directed graph $G=(V,E)$, and a node $r \in V$. Let $T_r$ be the set of spanning trees of $G$ with $r$ as root and all edges pointing to $r$. Is is it possible that there ...
3
votes
2answers
303 views

What was the name of that generalization of “Hall's marriage theorem”?

can sombody help me in graph theory? I just need to know the name of the generalization of Hall's marriage theorem... the one that states that if I have a bipartite graph between set $A$ with $n$ ...
3
votes
2answers
1k views

What's an intuitive explanation of the max-flow min-cut theorem?

I'm about to read the proof of the max-flow min-cut theorem that helps solve the maximum network flow problem. Could someone please suggest an intuitive way to understand the theorem?
0
votes
2answers
157 views

Count the number of paths in the Graph $P_3$. Provide a Proof by Induction using the Fibonacci sequence.

Consider the graph $P_3$ : $n_1$$ \rightarrow$ $n_2$$\rightarrow$ $n_3$$\rightarrow$ $n_4$ we count 6 paths of length k=1, namely: $n_1$ $\rightarrow$ $n_2$ $n_2$ $\rightarrow$ $n_3$ ...
1
vote
1answer
40 views

Is there any way to check if one graph is the result of identification and/or splitting on another graph?

Does some algorithm exist that can be used to check if graph $A$ and graph $B$ are related only by combining or separating vertices? Also, would this be possible if vertices had values (a vertex's ...
2
votes
0answers
86 views

Why is there no alpha-approximation algorithms for k-center problem where $\alpha<2$?

On page 39 of Design of Approximation Algorithms, the author argues this case with the dominating set problem. I can't understand it. A dominating set problem is a special case of the $k$-center ...
2
votes
1answer
116 views

Interval scheduling by minimum spanning tree

This is a homework and I'd like your feedback on whether I'm on the right track. Thank you. Problem: There's a project to build a railroad to connect $n$ cities. The railroad that connects any two ...
1
vote
0answers
133 views

Classifying graphs by patterns in their adjacency matrices

Given a set $S$, how can we classify different graphs $G(S)$ (tree, connected/disconnected, ...) based on the patterns of the 1's and 0's in their adjacency matrices $M(G(S))$?
1
vote
1answer
185 views

Probability of vertices in a complete bipartite graph being disconnected such that no path of length 2 remains between them?

My problem is the following. I have a set of vertices $N$ and a set of vertices $H$. Each vertex $n \in N$ is connected by means of an edge to each vertex $h \in H$. So the two sets of vertices and ...
2
votes
1answer
104 views

Lattices of Subgroups and Graph

In Dummit and Foote´s Abstract Algebra, when talking about the lattice of subgroups of $A_4$, the authors make the statement that, unlike virtaully all groups, $A_4$ has a planar lattice? My question ...
7
votes
2answers
111 views

Chromatic Number Identity Involving Edges

I'm trying the prove the following: Let $G$ be a simple graph with $m$ edges. Show that $\chi(G)\leq \frac{1}{2}+\sqrt{2m+\frac{1}{4}}.$ A very minute bit of algebraic manipulation shows that ...
1
vote
1answer
146 views

Sum in tree nodes - algorithm

I've got one very hard problem. Given a tree with nodes with integers. We need to find the largest sum of label values for a set of nodes which does not include any adjacent pair of nodes. ...
1
vote
1answer
989 views

Getting the shortest paths for chess pieces on n*m board

I originally posted this question of stackoverflow but I was suggested to post it here. So: I am stuck solving a task requiring me to calculate the minimal number of steps required to go from point A ...
3
votes
0answers
50 views

Defining a Certain Class of Plane Graphs

I'm having problems finding the right words to formulate the following class of graphs in a definition. I'm defining a class of plane graphs with the following properties: Removing any vertex of ...
2
votes
1answer
245 views

An attempt to prove Tutte's theorem

I'm studying Tutte's theorem. There is a proof in Graph Theory / Diestel. I took a very short glance at it before trying to prove it on my own. I am giving my proof attempt here with a specific ...
1
vote
2answers
146 views

Selecting balls from bags, with color restrictions

Suppose that I have N bags, each containing balls of a unique colour. What is the maximum number of pairs I can form without replacing the balls back in the bags and with the following constraints: ...
1
vote
2answers
499 views

Four color theorem, 3-regular planar graph, Hamiltonian path and spiral chains

Studying the four color problem, I was analyzing all possible 3-regular planar graphs of 12 faces, with the additional restriction that graphs that have one or more faces with less than 5 edges, are ...
0
votes
2answers
215 views

Friendship theorem and a group of 9 guests

Our task is to prove that there exists 4 strangers OR 4 friends within this group of 9 guests. Now what's the best way to go about finding this out? Using the Friendship Theorem? or using the ...
4
votes
0answers
188 views

Probability that a random weight function on $K_n$ satisfies the triangle inequality

On a complete graph $K_n$, every edge is assigned a random real weight in $[0, 1]$. I am trying to calculate the probability that the weights satisfy the triangle inequality or even bounds on this ...
0
votes
1answer
522 views

Proof of Turan's theorem

I'm following the proof of Turan's theorem on $\text{ex}(n,K^r)$ in Diestel's Graph Theory book (click to see the page) and something bothers me: Since $G$ is edge-maximal without a $K^r$ ...
2
votes
0answers
131 views

Expected number of monocolor triangles in random 2-coloring

So I have to color the edges of $K_6$ either red or blue. Let $X$ be the random variable that assigns to a coloring the number of monocolor triangles that can be found. (By monocolor triangle I mean ...
0
votes
1answer
107 views

Applications of graph colorings to discrete math

I'm looking for interesting examples of questions in discrete math that can be proved using graph colorings (as, for example existence of a particular division of people into $k$ distinct groups with ...
0
votes
1answer
199 views

What does face-width mean?

What is the meaning of the term face-width? I have seen the term used as a property of an embedding of a graph on a surface. I haven't found a definition.
3
votes
1answer
185 views

non existence of $K_{r,r}$ in a given graph on any number of vertices

I need to prove that: for every r>1 there exists $c>0$, s.t for every $n$, there exists some $G$, a graph on $n$ vertices, with average degree $cn^{1-\frac{2}{r}}$ (or above), s.t ...
3
votes
1answer
121 views

Ends of a Group

I have these two questions that I cannot get any intuition about. Perhaps someone can possibly offer a few hints on how to get started? 1) Show that the ends of ${\bf F_2} \oplus {\bf F_2}$ is equal ...
0
votes
1answer
86 views

What is the name of the symmetry of a bracelet transposition?

Take a bracelet with colored beads on it. Normally two bracelets belong to the same equivalence class under rotations and reflections. For an example, consider the bracelet denoted by the word ...
2
votes
0answers
47 views

Is there a name for the number of edges that need to be removed to lower the genus of a graph?

The number of edges that need to be removed from a graph to disconnect it is called the edge-connectivity. Similarly, given a graph of genus $n>0$, there is a minimum number of edges that you have ...
4
votes
0answers
226 views

Combinatorics and graph theory - counting connected graphs

We denote by $C(n,n+k)$ the number of connected graphs on $n$ vertices with $n+k$ edges. I have 2 problems I wish to prove, but after much effort have gotten nowhere with. I would greatly value some ...
1
vote
1answer
129 views

How does graph theory describe a sequence or line or path of nodes?

I have a dataset of pairs of map coordinates, and I suspect that they could be connected to make a path. However, I'm not sure what the end points are, or if the coordinates actually make a path. ...
3
votes
2answers
159 views

When is the dual graph simple?

This question is a follow-up and an improvement (I hope), to Is the dual graph simple? According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a ...
2
votes
1answer
622 views

Every $k$ vertices in an $k$ - connected graph are contained in a cycle.

Let $G$ be a $k$-connected graph. Meaning, $G$ has no less than $k$ vertices, and for every set of $k-1$ or less vertices, if we remove them from $G$, the graph stays connected (Of course, $G$ itself ...
2
votes
1answer
64 views

Every $2k$-regular contains a 2-factor

I need to prove that given a graph which is $2k$-regular, I can find a 2-factor. Meaning, There is a sub-graph of the above graph, which contains all vertices, and is 2-regular. I must say I have no ...
2
votes
2answers
233 views

A center of a graph (for example a tree) lies on its longest path

Prove a center of a tree (or if not much harder, of any graph) lies on the longest path. (I encountered this when I was reading an alternative proof for the property :"a tree has at most two ...
1
vote
1answer
48 views

Infinite families of Moore graphs

Is there another infinite family of Moore graphs besides the sequence of cycle graphs $C_{2d+1}$? (By definition a Moore graph must contain a cycle of length $2d+1$ where $d$ is its diameter, so ...
4
votes
0answers
81 views

Completeness of random walks in multiple dimensions?

I was reading Artificial Intelligence: Modern Approach (Norvig and Russell), and there was a footnote that really caught my attention. I apologize if the problem is more in the domain of CS than ...
7
votes
4answers
4k views

How to calculate the number of possible connected simple graphs with $n$ labelled vertices

Suppose that we had a set of vertices labelled $1,2,\ldots,n$. There will several ways to connect vertices using edges. Assume that the graph is simple and connected. In what efficient (or if there ...
8
votes
0answers
147 views

Branching processes and couplings

A text I am reading is discussing ways to couple branching processes, and describes the following 2 pairings, the latter of which I am failing to understand. (I include the former for the sake of ...
3
votes
1answer
72 views

Coloring points in a cycle

I have a question that relates to the Widom-Rowlinson model of statistical physics. Take a cycle on $n$ vertices. How many ways are there to color the $n$ vertices with the colors $\{\text{Red, ...
2
votes
2answers
71 views

Number of duplicate cases in graphs - hamiltonian and nonhamiltonian paths

Suppose that we set the number of vertexes in a graph (and suppose that in a graph, there is no subgraph separate or isolated from other subgraphs). Then, there are several ways to connect the ...
3
votes
2answers
511 views

maximum flow ford-fulkerson analysis

I am reading about maximum flows in Introduction to algorithms by Cormen etc. Ford-Fulkerson algorithm is given below. FORD-FULKERSON(G, s, t) ...
-2
votes
1answer
207 views

How to find the number of vertices and edges in these graphs?

How many vertices and edges are there in $K_{i,j}$ and $K_{i,j,k}$?
1
vote
2answers
180 views

Is the dual graph simple?

According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with $n\geq 0$ handles), one can define a dual ...
2
votes
1answer
411 views

Min-cut Max-flow $\Rightarrow$ Dilworth's theorem

Dilworth's theorem states that given a finite partially ordered set, the length of the maximal anti-chain, is equal to the minimal number of chains needed to partition the set. I need to prove that ...
7
votes
3answers
848 views

the Nordhaus-Gaddum problems for chromatic number of graph and its complement

Is there any relation between the chromatic number of a graph $G$ and its complement $G'$ that are always true? I saw these ones: $\chi(G)\chi(G')\geq n$ and $\chi(G)+\chi(G')\geq 2n$, but I'm not ...
2
votes
0answers
47 views

when is a net a net of a solid?

Assume that you are given a net of 6 squares. Is there a simple criterion (in terms of a few invariants that can be computed quickly) to tell whether it is the net of a cube? More generally, when is ...
0
votes
3answers
376 views

How many Euler tours exist in a given graph?

A Euler tour is defined like that: Let $G = (V, E)$ be a graph and $C$ a circuit in $G$. $C$ is called Euler tour $\Leftrightarrow$ every edge $e \in E$ is exactly once in the circuit. If a graph ...
1
vote
1answer
139 views

random graphs without cycles

Recall that a closed walk (in a undirected graph) is a cycle if its vertices are pairwise distinct. Does there exist random constructions of bipartite graphs without cycles with high probability?