Use this tag for questions in graph theory. Here a graph is a collections of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.
34
votes
2answers
499 views
Counting trails in a triangular grid
A triangular grid has $N$ vertices, labeled from 1 to $N$. Two vertices $i$ and $j$ are adjacent if and only if $|i-j|=1$ or $|i-j|=2$. See the figure below for the case $N = 7$.
How many trails ...
24
votes
0answers
313 views
Number of simple edge-disjoint paths needed to cover a planar graph
Let $G=(V,E)$ be a graph with $|E|=m$ of a graph class $\mathcal{G}$. A path-cover $\mathcal{P}=\{P_1,\ldots,P_k\}$ is a partition of $E$ into edge-disjoint simple paths. The size of the cover is ...
21
votes
7answers
8k views
Online tool for making graphs (vertices and edges)?
Anyone know of an online tool available for making graphs (as in graph theory - consisting of edges and vertices)? I have about 36 vertices and even more edges that I wish to draw.
(why do I have so ...
20
votes
3answers
810 views
An example of a real-world map that is not 4-colourable?
The four-colour mapping theorem states that all maps can be four-coloured (adjacent regions receive distinct colours, and four different colours are used in total). However, the technical definition ...
19
votes
5answers
379 views
Motivation for spectral graph theory.
Why do we care about eigenvalues of graphs?
There must be some reason. There is an entire mathematical discipline about them.
I always assumed that spectral graph theory is an extension of graph ...
18
votes
2answers
369 views
Cover time chess board (king)
Consider a random walk of a king on a standard chess board, which at each step moves to a uniformly random permitted square. What's the exact mean time to visit all squares (cover time), starting ...
18
votes
2answers
428 views
Groups and generating sets
This question feels completely trivial and I am somewhat embarrassed to be asking it, but I am having a brain dead moment and failing to prove what I'm sure is a completely trivial statement about ...
18
votes
2answers
397 views
Connecting a $n, n$ point grid
I stumbled across the problem of connecting the points on a $n, n$ grid with a minimal amount of straight lines without lifting the pen.
For $n=1, n=2$ it is trivial. For $n=3$ you can find the ...
17
votes
3answers
267 views
Why should “graph theory be part of the education of every student of mathematics”?
Until recently, I thought that graph theory is a topic which is well-suited for math olympiads, but which is a very small field of current mathematical research with not so many connections to ...
17
votes
1answer
1k views
The $n$ Immortals problem.
I saw this riddle posted on reddit a long time ago, called the "Seven Immortals."
In the beginning, the world is inhabited by seven immortals, ageless and sexless, who begin to multiply and ...
17
votes
3answers
814 views
Self-avoiding walk on $\mathbb{Z}$
How many sequences $a_1,a_2,a_3,\dotsc$, satisfy:
i) $a_1=0$
ii) ($a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$)
iii) $a_i\neq a_j$ for $i\neq j$
iiii) $\mathbb{Z}=\{a_i\}_{i>0}$
Are the two alternating ...
16
votes
4answers
2k views
Logic question: Ant walking a cube
There is a cube and an ant is performing a random walk on the edges where it can select any of the 3 adjoining vertices with equal probability. What is the expected number of steps it needs till it ...
16
votes
1answer
385 views
How to create mazes on the hyperbolic plane?
I'm interested in building maze-like structures on the [5, 4] tiling of the hyperbolic plane, where by maze-like I mean something akin to a spanning tree of the underlying lattice: a subgraph of the ...
16
votes
2answers
475 views
Does Birkhoff - von Neumann imply any of the fundamental theorems in combinatorics?
I recently had the occasion to think about Hall's Marriage Theorem for the first time since my undergraduate combinatorics class more than a decade ago. Reading the wikipedia article linked above, I ...
16
votes
1answer
1k views
What do the eigenvectors of an adjacency matrix tell us?
The principal eigenvector of the adjacency matrix of a graph gives us some notion of vertex centrality.
What do the second, third, etc. eigenvectors tell us?
Motivation: A standard information ...
16
votes
2answers
1k views
Human checkable proof of the Four Color Theorem?
Four Color Theorem is equivalent to the statement: "Every cubic planar bridgeless graphs is 3-edge colorable". There is computer assisted proof given by Appel and Haken. Dick Lipton in of his ...
15
votes
2answers
715 views
Not lifting your pen on the $n\times n$ grid
The question I am asking has basically already been asked. Please see this MSE thread. There are a few questions brought up on that thread, and a smaller number were answered. The reason I am ...
15
votes
2answers
478 views
If $G$ is biconnected and $\delta(G) \geq 3 \Rightarrow \exists v: G-v$ is also biconnected.
If $G$ is biconnected and $\delta(G) \geq 3 \Rightarrow \exists v: G-v$ is also biconnected.
Where $\delta (G) - $ minimum degree of all vertices, $G-v$ is equal to if we remove this vertex from $G$
...
14
votes
3answers
3k views
Average Scrabble graph structure: diameter?
Tonight a game of Scrabble ended in what I consider a very unusual graph structure,
unlike this generic web image, which seems more typical:
...
14
votes
2answers
633 views
Do your friends on average have more friends than you do?
I was watching this TED talk, which suggested that on average your friends tend to individually have more friends than you do. To define this more formally, we are comparing the average number of ...
14
votes
1answer
301 views
What are all conditions on a finite sequence $x_1,x_2,…,x_m$ such that it is the sequence of orders of elements of a group?
My Definition: The finite sequence $x_1,x_2,...,x_m$ of nonnegative integers, is said to be generated by the finite group $G$ iff
$n:=|G|=x_1+x_2+...+x_m$.
$n$ has $m$ divisors.
if ...
14
votes
2answers
509 views
What is the probability that every pair of students studies together at some point?
A cohort in a school consists of 75 students who study for 6 years. Each year, the students are randomly distributed into 3 classrooms of 25 students each. What is the probability that, after 6 ...
14
votes
2answers
163 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 ...
13
votes
4answers
708 views
Are these 2 graphs isomorphic?
They meet the requirements of both having an = number of vertices (7)
They both have the same number of edges (9)
They both have 3 vertices of deg(2) and 4 of deg(3)
However, graph two has 2 ...
13
votes
1answer
551 views
Did the Appel/Haken graph colouring (four colour map) proof really not contribute to understanding?
I hope this isn't off topic - sorry if I'm wrong.
In 1976, Kenneth Appel and Wolfgang Haken proved the claim (conjecture) that a map can always be coloured with four colours, with no adjacent regions ...
13
votes
7answers
1k views
What are good books to learn graph theory?
What are some of the best books on graph theory, particularly directed towards an upper division undergraduate student who has taken most the standard undergraduate courses? I'm learning graph theory ...
13
votes
2answers
687 views
Automorphisms of the Petersen graph
I am trying to find out the automorphism group of the Petersen graph. My book carries the hint: "Show that the $\tbinom{5}{2}$ pairs from {1, . . . , 5} can be used to label the vertices in such a way ...
13
votes
3answers
256 views
Exceptional books on real world applications of graph theory.
What are some exceptional graph theory books geared explicitly towards real-world applications?
I would be interested in both general books on the subject (essentially surveys of applied graph ...
13
votes
1answer
202 views
Help with a Bollobás proof - Switching between random graph models
I'm trying to make my way through Bollobás' book 'Models of Random Graphs', and unfortunately I've come entirely unstuck on one of his typical 2-line "and of course, this is entirely trivial"-style ...
11
votes
3answers
405 views
Counterexamples to proofs of correct statements
This question is in part inspired by a quote I saw in an answer to another question:
The problem with incorrect proofs to correct statements is that it is hard to come up with a counterexample.
...
11
votes
2answers
300 views
Is there a reason why the number of non-isomorphic graphs with $v=4$ is odd?
I am working through Trudeau's Introduction to Graph Theory, which contains the following problem:
In the following table, the numbers in the second column are mostly even. If we ignore the first ...
11
votes
1answer
265 views
Is it true that a connected graph has a spanning tree, if the graph has uncountably many vertices?
I found a proof that every connected graph (possibly infinite) has a spanning tree in Diestel's Graph Theory (Fourth Edition), Ch. 8 that uses Zorn's Lemma, but at a crucial step it seems to be ...
11
votes
3answers
462 views
Two seemingly unrelated puzzles have very similar solutions; what's the connection?
I think it's an interesting coincidence that the locker puzzle and this puzzle about duplicate array entries (see problem 6b) have such similar solutions. Spoiler alert! Don't read on if you want to ...
11
votes
1answer
239 views
In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?
Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard?
For example:
$M = 2, N = 2$, ans $= 6$
$M = 3, ...
10
votes
2answers
140 views
Integer sequences which quickly become unimaginably large, then shrink down to “normal” size again?
There are a number of integer sequences which are known to have a few "ordinary" size values, and then to suddenly grow at unbelievably fast rates. The TREE sequence is one of these sequences, which ...
10
votes
1answer
193 views
Is there a Hamiltonian path for the graph of English counties?
The mainland counties of England form a graph with counties as vertices and edges as touching borders. Is there a Hamiltonian path one can take? This is not homework, I just have an idea for a holiday ...
10
votes
4answers
245 views
Number of possibilities to cross a hexagonal lattice.
An ant walks along the line segments in the hexagonal lattice shown, from start to finish. The ant must go in the direction shown if there is an arrow, and never goes on the same line segment twice. ...
10
votes
3answers
860 views
Homology and Graph Theory
What is the relationship between homology and graph theory? Can we form simplicial complexes from a graph $G$ and compute their homology groups? Are there any practical results in looking at the ...
10
votes
2answers
401 views
Seating friends around a dinner table
This problem came from a Putnam problem solving seminar.
If each person in a group of n people is a friend of at least half the people in the group, then show that it is possible to seat the n ...
10
votes
1answer
3k views
Is Sage on the same level as Mathematica or Matlab for graph theory and graph vizualization?
The context:
I'm going to start working on a project that involves running predefined algorithms (and defining my own) for very big graphs (thousands of nodes). Visualization would also be welcome if ...
10
votes
1answer
171 views
Graph theory question
Here is an exercise from the book by Bondy/Murty that I am not quite able to understand.
Show that every simple graph has a vertex $x$ and a family of $\left\lfloor\frac{1}{2}d(x)\right\rfloor$ ...
10
votes
2answers
570 views
Diameter of a graph when removing a non-cut edge
It appears plausible to me that if we have a connected graph $G$ with diameter $d$ and we remove a non-cut edge $e$ from it, the diameter of the resulting graph $G_e$ will be at most $2d$.
By ...
10
votes
1answer
242 views
Is this similarity between trees and vector space bases just a coincidence?
A vector space basis is a set of vectors that span the space and is linearly independent.
It is well-known that for finite dimensional vector spaces this is equivalent to:
The set is minimal with ...
10
votes
1answer
226 views
What does the minimal eigenvalue of a graph say about the graph's connectivity?
I'm reading Fan Chung's Spectral Graph Theory, and I'm now in chapter 2. There, Chung proves Cheeger's inequality, which is that $2h_G \geq \lambda_1 > h_G^2/2$ for any graph $G$. To me, this ...
10
votes
1answer
492 views
Hamiltonicity of $G^2$
I am going through a proof of hamiltonicity of $G^2$ and stuck quite in the beginning.
Some definitions:
$G$ is a finite non-hamiltonian 2-connected graph, $C$ is a cycle in $G$, $D$ is a component ...
10
votes
2answers
165 views
Embedding the Infinite Binary Tree in Regular Tilings
Consider the regular tiling $(m,n)$ in which $m$ $n$-agons meet at each vertex. Most of the time this tilings have to "live" in the hyperbolic plane. The edges of its polygons define a graph where two ...
10
votes
2answers
514 views
Partition a binary tree by removing a single edge
The question is :
B-3 Bisecting trees
Many divide-and-conquer algorithms that operate on graphs require that the graph
be bisected into two nearly equal-sized subgraphs, which are induced by a ...
10
votes
1answer
283 views
How to “explain” Szemerédi's Regularity Lemma so that classmates may understand its value?
I am a student, preparing myself for a talk in which I want to present and prove Szemerédi's Regularity Lemma. I understand the proof and I am able to reproduce it - that is no problem. But I am ...
10
votes
0answers
226 views
Normalizers of automorphism groups
In abstract groups $\Gamma$ the normalizer $N_\Gamma(S)$ of a subset $S\subseteq\Gamma$ is the subgroup of all $x \in \Gamma$ that commute with $S$, i.e. $xS = Sx$, i.e. $x\ y\ x^{-1} \in S $ for all ...
10
votes
0answers
177 views
Is Erdös' lemma on intersection graphs a special case of Yoneda's lemma?
Under which name is the following proposition filed actually:
Every poset $P$ embeds fully and faithfully in the powerset of $P$,
ordered by subset inclusion.
Let me call it Dedekind's lemma. ...
