# Tag Info

Accepted

### Does minimal degree $n$ imply a $K_n$ minor

No. The edge-graph of the icosahedron is regular of degree five, but does not have a $K_5$ minor because it is planar (Kuratowski's theorem).
• 12.8k

### Does minimal degree $n$ imply a $K_n$ minor

More generally, it is a classic result (independently due to Kostochka and Thomason) that minimum degree $(\alpha+o(1))n \sqrt{\log n}$ suffices to force a $K_n$ minor, where $\alpha$ is an explicit ...
• 31.8k
Accepted

### Does every $4$-connected nonplanar graph contain a $K_5$-minor?

Yes, this is true and follows from Wagner's theorem. Wagner's theorem asserts that every graph with no $K_5$ minor can be built from $0$-, $1$-, $2$-, and $3$-sums from planar graphs and a fixed $8$ ...
• 31.8k
Accepted

### Menger's theorem with restrictions on where the paths can begin and end

There is no known necessary and sufficient condition like in Menger's theorem. However, there is a polynomial-time algorithm that decides if the paths exist. This is one of the main results of the ...
• 31.8k
Accepted

### Hadwiger number and minimal degree

No, icosahedron does not have $K_5$ as a minor being planar graph.
• 105k
Accepted

• 6,046
Accepted

### Minors of graphs with infinite chromatic number

For every such $G$ there is an $M$ satisfies your requirement. It is enough to show that for every graph $G$ with infinite chromatic number has two minors $G_{0}$ and $G_{1}$ such that $(i)$ $G_{0}$...
• 470
Accepted

• 27.7k
Accepted

### Are K_t-minor free graphs on small vertex sets understood?

There is no known straightforward answer, but pseudorandom graphs must come into the answer. See the paper by Myers and Thomason. [In response to the comment below] Look at recent papers by Postle--...
• 1,273
Accepted

### $|G|/\alpha(G) \leq \eta(G)$ where $\eta(G)$ is the Hadwiger number

This weakening is still an open question, even in the very special case of graphs with $\alpha(G)=2$ (complements of triangle-free graphs). In other words, do all graphs with independence number two (...
Accepted

### Identifying two non-adjacent vertices and the effect on the Hadwiger number

Identify two opposite vertices of the cycle graph $C_4$. This reduces the Hadwiger number from 3 to 2.
• 24.7k

### Does anyone know a specific polynomial-time algorithm to detect if a given signed graph contains an odd-K4 as a signed minor?

As a consequence of [Seymour, P.D., The matroids with the max-flow min-cut property, JCT B, 23 (1977), p. 189-222], a finite signed graph has an odd $K^4$ as signed minor if and only if the ...
• 6,031
Accepted

### Graph minors, and Kronecker product

The diamond cubic is a subgraph of the Kronecker product of three infinite paths, and $K\times K\times K$ patches of the diamond cubic are subgraphs of the Kronecker product of three length-$K$ paths. ...
• 18.5k