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

4
votes
2answers
288 views

The human brain — what kind of graph would it be?

I've read an article about a comparison between human brain and artificial neural networks. It's said that human brain contains $\approx 10^{11}$ neurons and each neuron is connected to $\approx 10^4$ ...
4
votes
1answer
228 views

Four Color Theorem

My wife is making a quilt. She has a whole bunch of colors and is making a very simple pattern. I enjoy watching the whole process because it's very mathematical, but it has made me question the four ...
0
votes
2answers
750 views

Petersen graph prolems

The last week I started to solve problems from an old russian collection of problems, but have stick on these 4: 1) Prove(formal) that Petersen graph has chromatic number 3(meaning that its vertices ...
1
vote
1answer
130 views

Black and Yellow edges and Shortest path

Given directed and weighted graph $G=(V,E)$ . There is no negative weighted edge . Each edge is colored (black or yellow). I need to find an algorythm the find the shortest path for a given $s\in V$ ...
1
vote
2answers
103 views

Data structure for graph, algorithm

I'm practicing solving programming problems in free time. This problem I spotted some time ago and still don't know how to solve it: For a given undirected graph with $n$ vertices and $m$ edges ...
1
vote
1answer
63 views

Searching the tree, proof

Let $G = (V,E)$ be undirected and connected graph and let $u\in V$. Let $DFS(u)$ and $BFS(u)$ be trees of searching $G$ by algorithms DFS and BFS respectively(starting from $u$). Prove that: ...
0
votes
1answer
41 views

Trivial case of $s \in T$

I was reading paper A Formal Basis for the Heuristics Determination of Minimum Cost Paths in section B "Some Definition About Graphs" there is footnote that say "We exclude the trivial case of $s \in ...
-3
votes
1answer
94 views

Graph theory basics: the size of a vertex set of a regular graph and a graph with $\Delta=4$.

Can someone tell me the answer to these? Determine $|V|$ given that $G(V,E)$ is a regular graph with $E=12$. If $G(V,E)$ be connected undirected graph what is largest value of $|V|$, if $|E|=19$ ...
3
votes
1answer
65 views

Smallest Number of Sets of Independent Edges in Sparse Graph

I have a very sparse undirected graph. I need to decompose it into n sets of edges. In each of these sets, all edges are independent (no two edges share any ...
-2
votes
1answer
65 views

A problem in graph theory related to the chromatic number

Prove that if $G$ is connected, not the complete graph and $\Delta(G) > 2$ then the chromatic number of G is at most $\Delta(G)$.
0
votes
1answer
110 views

A problem related to the SDR

Let $A_1, A_2, \ldots, A_{20}$ be twenty sets each of size $20$ such that $|A_i \cap A_j | \le 2$. Prove that they have a system of distinct representatives.
4
votes
2answers
71 views

Quantifying change in a graph

I need to a way to express a change in the structure of a given graph G, such that the original graph is G and the changed graph ...
1
vote
1answer
75 views

Is this face inside or outside the Hamilton cycle?

Assume a planar graph with a Hamilton cycle (depicted in green). $\hskip2in$ There are two possiblities for the displayed vertices to show up al0ng the Hamilton cycle: $\dots ef\dots xy\dots$ ...
2
votes
1answer
218 views

Generating non-isomorphic graph by adding two edges to a fixed graph

I am given a graph $G$ a fixed vertex $v \in V(G)$ and sets $S_1,S_2 \subseteq V(G).$ The problem I am currently studying requires to answer the following question Compute all non-isomorphic ...
1
vote
2answers
106 views

Connected graph proof

If a graph has $u > 3$ vertices and for every integer $k$ which satisfies the inequality $1\le k<\frac{u-1}{2}$, the number of vertices whose degree does not exceed $k$ is less than $k$, then ...
2
votes
0answers
84 views

Graph Theory: Help with a definition

I need some help to see if the definition I found of Cycles and Cycles Decomposition is right, here it is: A graph is a Cycle if it is isomorph to another graph $G=(V,E)$ with the following ...
2
votes
4answers
141 views

Consider the sequence 01110100…

Consider the sequence 01110100 as being arranged in a circular pattern. Notice that every one of the eight possible binary triples: 000, 001, 011, . . . , 111 appear exactly once in the circular list. ...
-1
votes
1answer
194 views

k-edge-connected graph problem

Could somebody help to solve this problem: Prove or disprove: If $G$ is a k-edge-connected graph with nonempty disjoint subsets $S_{1}$ and $S_{2}$ of $V(G)$, then there exist $k$ edge-disjoint paths ...
1
vote
0answers
144 views

Probability that a random graph is an expander

I have a random graph $G = (V, E)$ and each edge is in the graph with probability $p$. I need to show that the probability that $G$ is $\delta$-edge-expander* when $\delta= \frac{np}{4}$ goes to $1$ ...
3
votes
1answer
58 views

Enumerating simultaneous combinations in set

I have a group of 6 objects, that I want to put into 2 groups of 3. I know there are 20 combinations, but simultaneously there are only 10 combinations as the others are redundant. How do I ...
2
votes
2answers
450 views

Prove that if there exists two distinct paths from u to v,There exists a simple circuit

Let u and v be distinct vertices of a graph.Prove that if there exists at least two distinct paths in the graph from u to v ,then the graph contains a simple circuit. .I have started by defining a ...
14
votes
3answers
266 views

For a graph $G$, why should one expect the ratio $\text{ex} (n;G)/ \binom n2$ to converge?

$\text{ex} (n;G)$ is the maximal number of edges of a graph of order $n$ can have without containing $G$ as a subgraph. There are theorems saying what the limit actually is. But my lecture notes ...
5
votes
1answer
256 views

Walks of Even Length on a Bipartite Graph

Given a random walk on a simple $d$-regular bipartite graph $G$. The adjacency matrix $A'$ of $G$ may be split into blocks $$ A'=\pmatrix{ 0 &A^T\\ A&0 }, $$ The propagation operator $M=A'/d$ ...
1
vote
1answer
176 views

Using shortest paths as graph invarients for isomorphism. Where does the method fail?

Looking into the graph isomorphism problem, after trying to use vertex degree values as anchors for determining isomorphism (Of course failing with regular graphs), the next obvious target was ...
2
votes
1answer
470 views

bipartite graph - sufficient and necessary conditions

Sorry for a silly question, I got confused with the definition of bipartite graph. What is a necessary and sufficient condition for a bipartite graph. ...
2
votes
0answers
64 views

Convex polyhedral decomposition of spheres

Is there a decomposition of $S^2$ into $k$ (geodesically) convex polyhedra that are congruent to each other? What about $S^n$ for $n>1$? Remarks: A polyhedron is defined as an area enclosed by a ...
7
votes
2answers
135 views

Islands game and graph theory

I'm trying to recreate an electronic version of the game shown below: The game is basically a connected graph, with the number representing the compulsory degrees of each vertex. The player must ...
4
votes
1answer
79 views

Minimum size of spanning tree or seperator

Given a graph $G$ on $n$ vertices and vertex subsets $A_1, A_2, ... A_k$, is it always the case that there is either a tree of size at most $\sqrt{n}$ that intersects every $A_i$, or a set $S$ of size ...
2
votes
2answers
153 views

Are infinite cycle graphs just “straight lines”?

Are infinite cycle graphs just "straight lines"? I mean are they of the form: $\cdots \bullet - \bullet - \bullet - \bullet - \bullet - \cdots $
7
votes
5answers
203 views

asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one

A recent discussion, which may be found here, examined the problem of counting the number of acyclic digraphs on $n$ labelled nodes and having $k$ edges and indegree and outdegree at most one. It was ...
1
vote
2answers
128 views

Graph Theory proof

I need to make a proof but I can't come to the solution: For every vertex of oriented graph with vertices $U_{1},U_{2},\ldots,U_{n}$ we've got $s_{+}(U)$ the number of edges, which come to the vertex ...
7
votes
1answer
552 views

When does the adjacency or incidence matrix of a graph have consecutive ones property?

Given a graph, what are some sufficient (and necessary) conditions to tell if its adjacency matrix has the consecutive ones property? Similar question for its incidence matrix? Note that a ...
2
votes
1answer
920 views

Checking if my proof for path and walk in graph theory is correct

I am trying to prove that if there exists a walk in a graph from $v$ to $w$, then there exists a path in the graph from $v$ to $w$ where $v$ and $w$ are vertices of graph $g$... I am not sure if I ...
6
votes
3answers
248 views

Number of acyclic digraphs on $[n]$ with $k$ edges and each indegree, outdegree $\leq 1$

How many (labelled) acyclic digraphs are there on the vertex set $[n]$ with exactly $k$ edges and each indegree, outdegree $\leq 1$? The answer is $${n \choose k} {n-1 \choose k} k!.$$ Is there a ...
1
vote
2answers
105 views

Number of Vertices of Graphs

So, I was looking at some graph theoretical stuff, more specifically Topological Graph Theory, and I had a question about the definition of graphs: is there usually a condition in the definition ...
7
votes
2answers
191 views

Graphs with commuting adjacency matrices

Let A and B be adjacency matrix of two undirected simple graphs. Can we assign some combinatorial interpretations to this pair of graphs if A and B commute?
2
votes
0answers
44 views

maxcut and the minimal eigenvalue

For an adjacency matrix $A$ that represent a graph $G=\langle V,E\rangle$, I need to show that the maxcut is bounded by: $$ \mathrm{maxcut} \leq \frac{1}{2}|E| - \frac{|V| \lambda_{\min}(A)}{4}, $$ ...
9
votes
4answers
184 views

Graph on the cover of Bollobás's “Combinatorics”

I was browsing the library and I found Bela Bollobás book "Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics" and, on its cover, it has a graph that I don't ...
6
votes
1answer
286 views

Proving that the characteristic polynomial of a bipartite graph has alternating positive and negative coefficients

It is well known that the characteristic polynomial of a bipartite graph is of the form $\sum_{k=0}^n (-1)^kc_{2k} x^{2k}$ where $c_{2k} \geq 0$. I can prove why there cannot be any odd powered ...
1
vote
0answers
87 views

Minimum cost path with variable costs and fixed number of steps

I'm facing with the following problem. Suppose to have a generic oriented graph with curl (there can be an edge from a node to itself). Suppose also that you have to perform a $n$-vertices-long ...
0
votes
1answer
384 views

Induction on Menger's theorem by Diestel in Graph Theory

How does exactly the induction go in the proof number one? What is the induction hypothesis there and what is the induction step? By the induction hypothesis, $G/e$ contains an $A–B$ separator ...
6
votes
2answers
247 views

Probability that an undirected graph has cycles

If we know the probability $P$ that there exists an edge between two vertices of an undirected graph, let's say $P= 1/v$, where $v$ is the number of vertices in the graph, what is the probability ...
4
votes
2answers
208 views

Graphs whose automorphism group is the cyclic group

I would like a good hint for the following problem that takes into account the position at which I am stuck. The problem is as follows Let $\mathbb{Z}_n$ be the cyclic group of order $n.$ Find a ...
2
votes
1answer
199 views

Ramsey Numbers and Graphs

The Ramsey number $R(G,H)$ of two graphs $G$ and $H$ is the smallest value $n$ such that any 2-coloring of the edges of $K_n$ contains either a red copy of $G$ or a blue copy of $H$ . The ...
2
votes
1answer
669 views

Question on proof of Euler's formula

For some reason I'm having a difficult time understanding the proof of Euler's formula. I'm fine right up until the end. Theorem: If $G$ is a connected plane graph with $V$ vertices, $E$ edges, and ...
1
vote
1answer
117 views

Number of paths that begin at vertex, traverse $3$ edges of cube and end furthest

Select a vertex $V$ of a cube. How many paths begin at $V$, traverse exactly $3$ edges of the cube, and end at the vertex furthest from $V$?
9
votes
2answers
559 views

Two Steps away from the Hamilton Cycle

Assume an at least $2$-vertex connected, cubic, bipartite, planar graph $G$ that contains a Hamilton cycle (HC) $abcdefg\dots yx\dots za$ (in fact $G$ would then have at least four HCs, see here; it ...
2
votes
2answers
518 views

Time series and social network analysis

I am interested about plotting graphs of a phenomenon and study it using tools from social network analysis. Suppose the nodes are time series, and that the links between the nodes are the correlation ...
0
votes
1answer
1k views

Chromatic Polynomials for Graphs

The chromatic polynomial of a graph $G$ is the polynomial $C_G(k)$ computed recursively using the theorem of Birkhoff and Lewis. The theorem of Birkhoff and Lewis states: $c_G(k) = c_{G-e}(k) - ...
1
vote
1answer
159 views

Expected value and probability

A random graph consisting of n vertices and k undirected edges is constructed by repeating the following step k times: Randomly choose 2 vertices without replacement from n vertices, and connect them ...