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

117
votes
9answers
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 ...
82
votes
1answer
2k 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 $\...
68
votes
16answers
76k 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 ...
47
votes
7answers
1k views

What is the optimal path between $2$ fixed points around an invisible obstructing wall?

Every day you walk from point A to point B, which are $3$ miles apart. There is a $50$% chance each walk that there is an invisible wall somewhere strictly between the two points (never at A or B). ...
44
votes
4answers
2k views

How does the divisibility graphs work?

I came across this graphic method for checking divisibility by $7$. $\hskip1.5in$ Write down a number $n$. Start at the small white node at the bottom of the graph. For each digit $d$ in $...
43
votes
16answers
26k 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 ...
42
votes
6answers
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 ...
41
votes
2answers
835 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 ...
38
votes
1answer
947 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$$ ...
33
votes
0answers
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 ...
31
votes
10answers
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 ...
31
votes
5answers
715 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, ...
31
votes
0answers
504 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 ...
30
votes
1answer
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 ...
30
votes
1answer
630 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$....
29
votes
1answer
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 ...
28
votes
1answer
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 ...
28
votes
1answer
613 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. ...
25
votes
10answers
5k 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 ...
25
votes
3answers
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 ...
25
votes
1answer
278 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 ...
25
votes
4answers
655 views

Is this graph connected

Define the following graph on the vertex set ${\mathbb N}_{\geq1}\>$: Two numbers $a$, $b\in {\mathbb N}_{\geq1}$ are connected by an edge (written $a \ \mathcal{R} \ b)$ if and only if $a+b \ | \...
24
votes
4answers
9k 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 ...
24
votes
13answers
11k views

Graph theory software?

Is there any software that for drawing graphs (edges and nodes) that gives detailed maths data such as degree of each node, density of the graph and that can help with shortest path problem and with ...
23
votes
4answers
8k 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 degree $2$ and $4$ of degree $3$. However, ...
23
votes
5answers
5k views

What's the relation between topology and graph theory

I read the Wikipedia articles for both topology, graph theory (plus topological graph theory). Does topology encompass also graph theory? Or topology is only about studying shapes while graph theory ...
23
votes
2answers
992 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 ...
22
votes
3answers
1k 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 ...
21
votes
1answer
2k 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 ...
21
votes
1answer
739 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 ...
21
votes
3answers
787 views

Math puzzle: 10 digit strings generations

There was a question in a math competition that I attended last year. At the end of competition, I realized that my answer was wrong for the question below and I have never been able to figure out how ...
21
votes
0answers
570 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 $...
20
votes
3answers
2k 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 "deeper"...
20
votes
2answers
955 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 ...
20
votes
2answers
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 ...
19
votes
4answers
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 ...
19
votes
2answers
659 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 ...
19
votes
1answer
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 ...
19
votes
2answers
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 ...
18
votes
3answers
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 ...
18
votes
2answers
985 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 ...
18
votes
5answers
13k 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 ...
18
votes
3answers
12k views

Graph terminology: vertex, node, edge, arc

Precisely speaking, what is the difference between the graph terms of ("vertex" vs. "node") and ("edge" vs. "arc")? I have read that "node" and "arc" should be used when the graph is strictly a tree. ...
18
votes
2answers
402 views

Generalized nontransitive dice

Let $X_1, \ldots, X_n$ be a collection of random variables. Consider the directed graph with vertex set $\{ 1, 2, \ldots, n \}$ where there is a directed edge $i \to j$ if $\mathbb{P}(X_i > X_j) &...
18
votes
2answers
517 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
601 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$ ...
18
votes
2answers
344 views

A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
18
votes
0answers
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. ...
17
votes
4answers
6k views

Why a complete graph has $\frac{n(n-1)}{2}$ edges?

I'm studying graphs in algorithm and complexity, (but I'm not very good at math) as in title: Why a complete graph has $\frac{n(n-1)}{2}$ edges? And how this is related with combinatorics?
17
votes
1answer
14k views

How does Tree(3) grow to get so big? Need laymen explanation.

I am not a mathematician but I am interested in big numbers. I find them to be really interesting, almost god-like. I am watching a series of videos from David Metzler on youTube. I have a basic ...