# Questions tagged [graph-theory]

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.

**6**

**4**answers

### Number of spanning trees in a grid

**0**

**3**answers

### min cut and max cut

**15**

**11**answers

### Chromatic number of graphs of tangent closed balls

**7**

**1**answer

### Graphs of Tangent Spheres

**34**

**21**answers

### Generalizations of Planar Graphs

**4**

**2**answers

### A graph connectivity problem (restated)

**43**

**4**answers

### Why are planar graphs so exceptional?

**0**

**1**answer

### Szemeredi's Regularity Lemma

**5**

**2**answers

### How are graph automorphisms are affected by transformations?

**5**

**5**answers

### A random walk matrix has eigenvalue 1 with multiplicty 1 - why?

**6**

**2**answers

### Difference between connected vs strongly connected vs complete graphs [closed]

**9**

**5**answers

### Triangle-free Lemma

**10**

**2**answers

### Ramsey Theory, monochromatic subgraphs

**8**

**4**answers

### Prime numbers $p$ not of the form $ab + bc + ac$ $(0 < a < b < c )$ (and related questions)

**20**

**6**answers

### “The” random tree

**16**

**3**answers

### Number theoretic spectral properties of random graphs

**11**

**12**answers

### Graphs with fractal properties?

**15**

**5**answers

### Which graphs have incidence matrices of full rank?

**0**

**2**answers

### What is the name for this type of graph? [closed]

**10**

**1**answer

### Is every matching of the hypercube graph extensible to a Hamiltonian cycle

**6**

**2**answers

### Algorithms for laying out directed graphs?

**0**

**3**answers

### Where to find nice diagrams of trees and other graphs? [closed]

**12**

**3**answers

### Groupoid of moves on trivalent fatgraph

**7**

**1**answer

### Graphs with incidence matrices whose pseudoinverses are proportional to their transposes

**10**

**14**answers

### What introductory book on Graph Theory would you recommend?

**5**

**3**answers

### Erdős–Stone theorem type edge density estimates for bipartite graphs?

**3**

**3**answers

### Number of paths equal less than equal to a certain length

**2**

**1**answer

### Number of Shortest paths problem

**5**

**5**answers

### A walk on a compact 2D surface embedded in 3-space that never returns home

**8**

**3**answers

### Singularity of sparse random matrices

**5**

**2**answers

### Complexity of determining if two graphs have same cycle matroid?

**4**

**3**answers

### A name for a claw-graph with paths attached to it

**0**

**4**answers

### How do I iterate over binary trees?

**1**

**1**answer

### Edge-disjoint shortest paths

**5**

**1**answer

### Non trivial colouring of the edges of an infinite complete graph

**6**

**2**answers

### Infinite Ramsey theorem with infinitely many colours

**6**

**3**answers

### 'Focusing' the mass of the Probability Density Function for a Random Walk

**8**

**10**answers

### Interesting families of sparse graphs?

**0**

**2**answers

### Given a Spanning Tree and an Edge Not on the Spanning Tree, How to Form a Cycle Base?

**7**

**2**answers

### How can I prove that a sequence of squares of graph norms is never cyclotomic?

**7**

**2**answers

### Is there a free digraph associated to a graph?

**7**

**3**answers

### Special cases for efficient enumeration of Hamiltonian paths on grid graphs?

**2**

**5**answers

### Algorithm to Find all the Cycle Bases in a Graph

**12**

**3**answers

### Is there a matrix whose permanent counts 3-colorings?

**5**

**2**answers

### Smooth immersion(?) of graphs into the plane

**3**

**3**answers

### Boolean network as a gauge field

**6**

**3**answers

### Looking for cubic, bipartite graphs with girth at least six and no cycles of length 8.

**11**

**9**answers

### What is the Tutte polynomial encoding?

**12**

**5**answers

### Can one make Erdős's Ramsey lower bound explicit?

**5**

**3**answers