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

3,401 questions
2k views

### Number of spanning trees in a grid

Given a $\sqrt{n}\times\sqrt{n}$ piece of the integer $\mathbb{Z}^2$ grid, define a graph by joining any two of these points at unit distance apart. How many spanning trees does this graph have (...
2k views

### min cut and max cut

If you want to maximize a function f(x), you can do this by minimizing -f(x). Naively it seems like an analogous trick could convert a max cut problem into a min cut problem, however this is ...
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 ...
637 views

### Graphs of Tangent Spheres

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 circle packing whose graph is G. What ...
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; ...
329 views

### A graph connectivity problem (restated)

Given an undirected connected graph, our goal is to remove some edges to make the graph disconnected. The constraint is that each node of the graph can not lose more than $m$ edges incident to it. I ...