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

72
votes
1answer
1k 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 ...
36
votes
2answers
637 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 ...
34
votes
7answers
26k 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 ...
33
votes
4answers
1k 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 ...
26
votes
6answers
2k 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 ...
23
votes
4answers
561 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 \ | ...
22
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 ...
22
votes
1answer
7k 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 ...
22
votes
1answer
393 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 ...
21
votes
1answer
3k 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 ...
20
votes
9answers
6k 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 ...
19
votes
3answers
648 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 ...
19
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 ...
19
votes
2answers
474 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 ...
18
votes
4answers
3k 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, ...
18
votes
2answers
628 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
478 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
1answer
542 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 ...
18
votes
2answers
718 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 ...
17
votes
4answers
5k 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 ...
17
votes
3answers
725 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 ...
17
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 ...
17
votes
1answer
181 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 ...
17
votes
3answers
283 views

Results in graph theory proved using other areas of math, and vice versa

I'm curious about learning graph theory, as it seems to pop up in some unexpected places. In order to get a partial feel for the subject, I was wondering if anyone could point me to some survey ...
17
votes
2answers
859 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
2answers
793 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 ...
16
votes
2answers
321 views

Counting the number of polygons in a figure

I often come across figures like this on the net, or as contest problems, asking to find the number of a specific type of polygon in the figure (triangles, in this case). But I've never really found ...
16
votes
2answers
521 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$ ...
15
votes
1answer
813 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 ...
15
votes
9answers
6k 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 ...
15
votes
2answers
233 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 ...
14
votes
6answers
697 views

Can an algorithm be part of a proof?

I am an undergraduate student. I have read several papers in graph theory and found something may be strange: an algorithm is part of a proof. In the paper, except the last two sentences, other ...
14
votes
3answers
4k 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
3answers
286 views

Why there are $11$ non-isomorphic graphs of order $4$?

I'm new to graph theory and I don't plan to become a serious student of graph theory either. My book suggests that there are $11$ non-isomorphic graphs of order $4$, but I can't see why. I know that ...
14
votes
2answers
666 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
3answers
818 views

A problem I can't solve from my childhood to now.

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 ...
14
votes
2answers
271 views

Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

Post-Bounty Edit: Still no answer; will gladly accept if someone can provide a reference. Earlier Edit: It appears that the answer is "yes," either by an already existent publication or by ...
14
votes
1answer
347 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
524 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
254 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) ...
14
votes
2answers
527 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, ...
14
votes
3answers
254 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
3answers
298 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 ...
13
votes
3answers
662 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. ...
13
votes
2answers
441 views

“Planar” graphs on Möbius strips

Is there an easy way to tell if a graph can be embedded on a Möbius strip (with no edges crossing)? A specific version of this: if a simple graph with an odd number of vertices has all vertices of ...
13
votes
2answers
1k 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
468 views

Problem on bipartite graphs.

Let's $G$ is bipartite graph with sides $X=\{v_1,v_2,\ldots,v_n\}$ and $Y=\{u_1,u_2,\ldots,u_n\}.$ Let $|N_G(v_i)|=k$ and $|N_G(v_i)\cap N_G(v_j)|=d\lt k~,(i\ne j)$. Prove that $|N_G(u_i)|=k$ and ...
13
votes
1answer
654 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 ...
13
votes
3answers
348 views

Metal Ball Cage Template Cardinality: A Brilliantly Lazy PROOF

N.B. - I'm looking for the simplest way to ascertain the number of templates $T$ (see below) comprising the structure from just one angle alone; that is, I'm sitting down looking up at this thing, ...
13
votes
2answers
281 views

A question about the minesweeper game

This is just out of curiosity. Suppose the game has $m \times n$ boxes for positive integers $m$ and $n$. How can we make the sum of the numbers on a finished game the most? There are two extreme ...