# Tagged Questions

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.

15k views

### There are apparently $3072$ ways to draw this flower. But why?

This picture was in my friend's math book: Below the picture it says: There are $3072$ ways to draw this flower, starting from the center of the petals, without lifting the pen. I know ...
2k views

3k views

### Motivation for spectral graph theory.

Why do we care about eigenvalues of graphs? Of course, any novel question in mathematics is interesting, but there is an entire discipline of mathematics devoted to studying these eigenvalues, so ...
839 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 ...
995 views

### Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power

I've known that one can arrange all the numbers from $1$ to $\color{red}{15}$ in a row such that the sum of every two adjacent numbers is a perfect square. $$8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$ ...
1k views

### Connecting three houses to three utilities [duplicate]

When I was a child I was given this problem to send a wire from electricity, water, and internet to each of the houses, all three houses must have all three wires connected without being crossed over ...
10k views

### How do I explain the Königsberg Bridge problem to a child?

I am going to demonstrate the Königsberg seven bridge problem in a science exhibition. I am also going to use a model for a more visual representation of the problem. Now, how do I explain this (the ...
723 views

### A disease spreading through a triangular population

I have run into this problem in my research, which I'm presenting under a different guise to avoid going into unnecessary background. Consider a population that is connected in a triangular manner, ...
544 views

### What is that thing that keeps showing in papers on different fields?

A few months ago, when I was studying strategies for the evaluation of functional programs, I found that the optimal algorithm uses something called Interaction Combinators, a graph system based on a ...
2k views

### Is Wolfram wrong about unique 3-colorability, or am I just confused?

The illustration on Wolfram's page claims to present a uniquely colorable, triangle-free graph. However, this seems to be blatantly false: the graph has a symmetry with respect to a reflection through ...
636 views

### Zombie outbreak on a $k$-regular graph

Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$. There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability $p$....
13k views

### Is Sage on the same level as Mathematica or Matlab for graph theory and graph visualization?

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 ...
6k 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 ...
614 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. ...
6k views

### Is it possible to draw this picture without lifting the pen?

Some days ago, our math teacher said that he would give a good grade to the first one that will manage to draw this: To draw this without lifting the pen and without tracing the same line more than ...
1k 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 ...
284 views

### Smallest graph with automorphism group the quaternion $8$-group, $Q_8$

Frucht's Theorem states that for any finite group $G$ there is a finite (undirected) graph $\Gamma$ for which the automorphism group $\text{Aut}(\Gamma)$ of $\Gamma$ is isomorphic to $G$, and for many ...
656 views

25k views

### Graph theory: adjacency vs incident

Okay, so I think if 2 vertices are adjacent to each other, they are incident to each other....or do I have it wrong? Is this just different terminology. I thought I was totally clear on this for my ...
964 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 ...
2k 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 ...
999 views

### Not lifting your pen on the $n\times n$ grid

Does there exist $n$, and $r<2n-2$, such that the $n\times n$ square grid can be connected with an unbroken path of $r$ straight lines? Note: This has essentially already been asked - see this ...
670 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 ...
292 views

### Bombing of Königsberg problem

A well-known problem in graph theory is the Seven Bridges of Königsberg. In Leonhard Euler's day, Königsberg had seven bridges which connected two islands in the Pregel River with the mainland, laid ...
892 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 ...
1k views

### A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
8k views

### Difference between graph homomorphism and graph isomorphism

I am still not getting how graph isomorphism and homomorphism differ. Can anyone show me two graphs that are homomorphic, but not isomorphic? Also, Wikipedia says that when the function and the ...
14k 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 ...