**17**

votes

**8**answers

2k 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 ...

**-1**

votes

**1**answer

231 views

### an interesting conjecture about even cycle

Let G be a simple graph which is a $2n$-cycle equipped with $n$ chords such that $G$ is $3$-regular,in other words,the set of the $n$ chords is a perfect matching of $G$(that is,every vertex of $G$ is ...

**46**

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 ...

**42**

votes

**4**answers

4k 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 ...

**5**

votes

**1**answer

326 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 ...

**5**

votes

**1**answer

481 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 ...

**27**

votes

**16**answers

7k 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, ...

**24**

votes

**18**answers

8k 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 ...

**31**

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; ...

**27**

votes

**9**answers

2k 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.
...

**25**

votes

**4**answers

2k 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 ...

**10**

votes

**1**answer

786 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 ...

**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 ...

**15**

votes

**2**answers

816 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 ...

**9**

votes

**2**answers

831 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 ...

**6**

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 ...

**6**

votes

**1**answer

758 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

113 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 ...

**3**

votes

**1**answer

1k views

### Counting graphs

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.

**5**

votes

**2**answers

426 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

197 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

244 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

806 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 ...

**1**

vote

**0**answers

370 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

130 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

**0**answers

48 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 ...

**31**

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 ...

**30**

votes

**3**answers

5k 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, ...

**40**

votes

**4**answers

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

**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 ...

**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 ...

**40**

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 ...

**24**

votes

**3**answers

701 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 ...

**19**

votes

**1**answer

924 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 ...

**20**

votes

**5**answers

2k 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 ...

**15**

votes

**11**answers

1k 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 ...

**21**

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 ...

**12**

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$ ...

**24**

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 ...

**11**

votes

**3**answers

366 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 ...

**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 ...

**34**

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 ...

**22**

votes

**2**answers

2k views

### Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?

The following problem is homework of a sort -- but homework I can't do!
The following problem is in Problem 1.F in Van Lint and Wilson:
Let $G$ be a graph where every vertex
has degree $d$. ...

**20**

votes

**1**answer

2k views

### Monochromatic triangles in every two-coloring of the plane?

An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means ...

**13**

votes

**1**answer

771 views

### Is there a group whose cardinality counts non-intersecting paths?

Introduction
Graphs are not only important combinatorial objects, but also related to many topological/algebraic structures. In this question I am going to talk about various group structures with ...

**10**

votes

**3**answers

1k views

### Is non-connectedness of graphs first order axiomatizable?

A recent
question
asked for graph properties that are first order axiomatizable but not finitely axiomatizable.
Connectedness was mentioned in the context. Connectedness can be axiomatized in ...

**7**

votes

**12**answers

3k views

### Graphs with fractal properties?

For the purposes of a research project, I am wondering if there are any resources on graphs with fractal properties, by which I mean self-similarity in particular. For instance, imagine a graph where ...

**15**

votes

**3**answers

705 views

### Complexity of equitable partitions

We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the same cell, and any ...

**14**

votes

**1**answer

684 views

### Is every graph the center of some other graph?

The center of a graph $G$ is the set of vertices that minimize the largest
distance to vertices in $G$, e.g., in the graph below, that radius is $4$:
Define the ...