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

3
votes
1answer
545 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
1k 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
412 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
415 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
205 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
41 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
104 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
136 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
161 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
202 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
112 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
131 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
161 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
1k 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
296 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
158 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
1answer
619 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
249 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
195 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
678 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
148 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
117 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
242 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
189 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
129 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
94 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
286 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
153 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
186 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
930 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
82 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
326 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
54 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
109 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
6k 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 ...
9
votes
0answers
172 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
79 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
80 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
646 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
225 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
230 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
496 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 ...
8
votes
3answers
1k 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 ...
1
vote
0answers
55 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
643 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
156 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?
1
vote
1answer
836 views

Draw a graph from an incidence matrix in Excel

I am trying to study the social network of the center where I am working. I have done a compilation of relation between personal from programed meeting, formal working team, etc. to analyze structural ...