**19**

votes

**8**answers

3k views

### Representability of finite metric spaces

There have been a couple questions recently regarding metric spaces, which got me thinking a bit about representation theorems for finite metric spaces.
Suppose $X$ is a set equipped with a metric ...

**5**

votes

**1**answer

506 views

### Difference Sets

Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...

**0**

votes

**1**answer

276 views

### Does this graph contain at least two Hamiltonian cycles?

Let $G$ be a simple graph which is a $2n$-cycle together with $n$ chords such that $G$ is $3$-regular. In other words, the set of $n$ chords is a perfect matching of $G$.
I conjecture that for every ...

**47**

votes

**8**answers

5k views

### What is a continuous path?

I would like some help, because I am getting mad trying to answer the following
Question: Let $X$ be a topological space, what is a continuous path in $X$?
Well, maybe you're already getting ...

**30**

votes

**18**answers

10k views

### Interesting and Accessible Topics in Graph Theory

This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope ...

**45**

votes

**4**answers

5k views

### Connectivity of the Erdős–Rényi random graph

It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...

**7**

votes

**1**answer

1k views

### Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...

**6**

votes

**1**answer

388 views

### Infinite graphs isomorphic to their line graph

The only finite connected graphs $G$ that are isomorphic to their line graph $L(G)$ are the cycle graphs $C_n$ (see this link for example).
There are connected countable graphs that are isomorphic to ...

**34**

votes

**17**answers

8k views

### Linear Algebra Proofs in Combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...

**33**

votes

**20**answers

4k views

### Generalizations of Planar Graphs

This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...

**42**

votes

**12**answers

4k views

### Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors.
The purpose of this question is to collect generalizations, variations, and strengthenings of the four ...

**28**

votes

**9**answers

3k views

### How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?

Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...

**26**

votes

**4**answers

3k views

### Adjacency matrices of graphs

Motivated by the apparent lack of possible classification of integer matrices up to conjugation (see here) and by a question about possible complete graph invariants (see here), let me ask the ...

**18**

votes

**3**answers

722 views

### Why are Dynkin diagrams characterized by their eigenvalues?

The Dynkin diagrams An, Dn, E6,
E7, E8 can be characterized among finite simple connected
graphs by the property that their eigenvalues (that is, the eigenvalues of their adjacency matrices) all have ...

**10**

votes

**1**answer

864 views

### Different uses of the word “ergodic”

There appear to be two definitions of the word ergodic.
The dynamical systems definition says that a measure space $(X,\mathit B, \mu)$ and measure preserving transformation $T: X \mapsto X$ is ...

**10**

votes

**2**answers

949 views

### Is the Steiner ratio Gilbert–Pollak conjecture still open?

Gilbert-Pollak conjecture on the Steiner ratio: Consider a set $P$ of $n$ points on the euclidean plane. A shortest
network interconnecting $P$ must be a tree, which is called a Steiner minimum ...

**15**

votes

**2**answers

826 views

### Minimal graphs with a prescribed number of spanning trees

As its long ago since Erdős died and mathoverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem ...

**7**

votes

**2**answers

2k views

### Degree Sequences and Graph Enumeration

I do recreational math from time to time, and I was wondering about a couple of graph enumeration issues.
First, is it possible to enumerate all simple graphs with a given degree sequence?
Second, ...

**5**

votes

**4**answers

1k views

### Delaunay triangulations and convex hulls

This is a reference request.
I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you ...

**7**

votes

**1**answer

2k views

### Counting non-isomorphic graphs with prescribed number of edges and vertices

I'd love your help with this question.
Let $n\geq3$ be a fixed integer. How many non-isomorphic graphs with $p$ vertices and $q$ edges are there where $p+q=n$?
Thank you very much.
Crossposted at ...

**6**

votes

**1**answer

884 views

### Algorithm for embedding a graph with metric constraints

Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide if there is an ...

**4**

votes

**1**answer

123 views

### genus of a finite simple undirected graph

Let $G$ be a finite simple undirected graph. Suppose there exist subgraphs $G_1,G_2,\dots,G_n$ of $G$, such that $G_i$ and $G_j$, have no common edges and have at most two common vertices, for each ...

**2**

votes

**1**answer

2k views

### Can the first non-zero eigenvalue of a Laplacian matrix with more than 1 zero valued eigenvalue be used to reorder an adjacency matrix?

I have a graph with multiple connected components, and its adjacency matrix. I form the Laplacian matrix (wiki Laplacian matrix), and from the 1K nodes there around ...

**5**

votes

**2**answers

474 views

### Generalisations of Petersen's 2-factor theorem?

Petersen's 2-Factor Theorem (1891): A $(2r)$-regular graph can be decomposed into $r$ edge-disjoint $2$-factors.
I'd like to use this theorem (or a more general version of this theorem) to imply ...

**4**

votes

**1**answer

203 views

### Graphs with constant edge imbalance

The imbalance of an edge $(u,v) \in E(G)$ of a graph $G$ is defined as $|d(u)-d(v)|$ ($d$ being, as usual the degree). (This concept was introduced by Albertson in 1997)
I'm interested in the set of ...

**3**

votes

**1**answer

267 views

### Min Bend Orthogonal Knots

I am seeking literature on 3D orthogonal drawings of knots,
especially minimum bend drawings.
An orthogonal drawing employs segments parallel to the axes of
a Cartesian coordinate system.
A bend is a ...

**5**

votes

**3**answers

1k views

### Relationship between triangle free graphs and their minimum degree

Let $T$ be a triangle-free graph on $n$ vertices with minimum degree $\delta$ (which can be $0$). How does one show that $n >2\delta -1$? It seems to be true for bipartite graphs, but I cannot see ...

**5**

votes

**1**answer

338 views

### Crossing number of the Grötzsch graph

Related wikipage: http://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph
Is the crossing number of the Grötzsch graph known? I have heard it conjectured to be 5 (certainly it is no greater), but came up ...

**2**

votes

**2**answers

135 views

### Matching with probabilistic edges

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...

**1**

vote

**0**answers

376 views

### Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition

Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...

**1**

vote

**0**answers

133 views

### Non-trivial lower bound on the number of “Graph Diagonals”

The definition of Graph Diagonals, that are the subject of this question, is based on the notions of crossing edges and on connected graphs:
Two edges $AC$ and $BD$ of a complete, symmetric and ...

**0**

votes

**1**answer

128 views

### Infinite graph with degrees given

Let $\kappa$ be an infinite cardinal and suppose $$n, d: \kappa \to \big((\kappa+1)\setminus \{0\}\big) = \{1, \ldots, \kappa\}$$ are arbitrary functions.
Is there $E \subseteq \big\{\{x,y\}: x\neq y ...

**0**

votes

**0**answers

63 views

### Expected length of minimum spanning trees

For a simple, finite, connected and complete graph $K_n = (V(K_n), E(K_n))$ with vertex set $V(K_n)$ and edge set $E(K_n)$, we assign a non-negative independent and identical distributed random weight ...

**34**

votes

**15**answers

5k views

### Strengthening the Induction Hypothesis

Suppose you are trying to prove result $X$ by induction and are getting nowhere fast. One nice trick is to try to prove a stronger result $X'$ (that you don't really care about) by induction. This ...

**38**

votes

**4**answers

6k views

### Why are planar graphs so exceptional?

As compared to classes of graphs embeddable in other surfaces.
Some ways in which they're exceptional:
Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, ...

**41**

votes

**4**answers

7k views

### Do there exist chess positions that require exponentially many moves to reach?

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an ...

**20**

votes

**5**answers

3k views

### Complete graph invariants?

Obviously, graph invariants are wonderful things, but the usual ones (the Tutte polynomial, the spectrum, whatever) can't always distinguish between nonisomorphic graphs. Actually, I think that even a ...

**23**

votes

**3**answers

1k views

### Some models for random graphs that I am curious about

G(n,p)
We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This ...

**21**

votes

**5**answers

3k views

### The Matrix-Tree Theorem without the matrix

I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me ...

**19**

votes

**1**answer

986 views

### A Question on 1, 2 ,3 Conjecture

The 1, 2, 3 conjecture is well-known:
If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the ...

**24**

votes

**3**answers

757 views

### Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...

**6**

votes

**1**answer

724 views

### Reconstruction Conjecture: Group theoretic formulation

As we read from wiki, informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs.
Is there a group-theoretic formulation of this ...

**15**

votes

**11**answers

2k views

### Chromatic number of graphs of tangent closed balls

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What ...

**13**

votes

**3**answers

1k views

### A question on representation of graphs

Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...

**12**

votes

**3**answers

638 views

### Models for graphs representing real-life networks

I am interested in basic models of graphs (stochastic or deterministic) that are offered for real-life networks (like social networks, the Internet, neuron networks).
I will be thankful for answers ...

**23**

votes

**2**answers

2k views

### An unfair marriage lemma

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem:
Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...

**20**

votes

**3**answers

2k views

### What is this subgroup of $\mathfrak S_{12}$?

On some occasion I was gifted a calendar. It displays a math quizz every day of the year. Not really exciting in general, but at least one of them let me raise a group-theoretic question.
The quizz: ...

**37**

votes

**6**answers

3k views

### Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...

**26**

votes

**9**answers

3k views

### Is the empty graph a tree?

This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed.
The ...

**9**

votes

**3**answers

1k views

### The diameter of the Erdös component of the collaboration graph

This site claims that the diameter of the Erdös component of the collaboration graph in 2004 was 23. What is it now? Is it increasing or decreasing with time? Recall that the vertices of the ...