# Tagged Questions

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.

learn more… | top users | synonyms

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 83, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9404004812240601, "perplexity_flag": "middle"}