Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options not deleted
user 2233
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.
56
votes
21
answers
14k
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, …
49
votes
15
answers
11k
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 h …
48
votes
5
answers
8k
views
Algebraic proof of 4-colour theorem?
4-colour Theorem. Every planar graph is 4-colourable.
This theorem of course has a well-known history. It was first proven by Appel and Haken in 1976, but their proof was met with skepticism because …
- 32.1k
36
votes
Accepted
Can one measure the infeasibility of four color proofs?
To answer the question it is important to disentangle the proof as follows.
Theorem 1. Every minimum counterexample to the 4CT is an internally 6-connected triangulation.
Theorem 2. If $T$ is a min …
- 32.1k
32
votes
Accepted
Function of $(x_1,x_2,x_3,x_4)$ that factors in two ways as $\phi_1 (x_1 ,x_2 )\phi_2(x_3 ,x...
Here is a fairly straightforward proof which also proves various generalizations of your problem. Choose $c,d$ such that $\phi_2(c,d) \neq 0$. If no such $c,d$ exist, then $f$ is identically $0$ and …
- 32.1k
31
votes
Obstructions for embedding a graph on a surface of genus g
I'll just remark that the fact that every surface has a finite number of excluded minors (and also topological minors) does not require the full strength of the Graph Minors Theorem. Indeed, the proo …
- 32.1k
28
votes
Can a problem be simultaneously polynomial time and undecidable?
As others have mentioned, the answer to your title question is strictly speaking no. With regards to your other questions, it has been proven that it is undecidable to compute the excluded minors for …
23
votes
Counting non-isomorphic graphs with prescribed number of edges and vertices
Using the Combinatorica package in Mathematica, the command NumberOfGraphs$[p,q]$ returns the number of non-isomorphic graphs with $p$ vertices and $q$ edges. If you want to implement this yourself, …
- 32.1k
23
votes
Accepted
Realizing groups as automorphism groups of graphs.
According to the wikipedia page, every group is indeed the automorphism group of some graph. This was proven independently in
de Groot, J. (1959), Groups represented by homeomorphism groups, Mathem …
- 32.1k
22
votes
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 c …
- 32.1k
20
votes
Menger's theorem via matroids
There is indeed a Menger's theorem for matroids first proven by Tutte. The reference is
Tutte, W. T., Menger’s theorem for matroids, Journal of Research of the National
Bureau of Standards—B. M …
- 32.1k
19
votes
3
answers
995
views
Drawing planar graphs with integer edge lengths
It is well known that every planar graph has an embedding such that every edge is drawn as a straight line segment (Fáry's Theorem). Kemnitz and Harborth made the following stronger conjecture
Conje …
- 32.1k
19
votes
Is there a version of König's theorem for tripartite 3-graphs?
This is a special case of Ryser's Conjecture, which states that in
an $r$-partite, $r$-uniform hypergraph (with $r>1$)
$\tau \leq (r-1) \nu$,
where $\tau$ is the size of a minimum cover and $\ …
- 32.1k
17
votes
Accepted
Can all crossings in a graph be moved to one point?
No, this is not always possible.
Lemma. Let $G$ be an $n$-vertex graph with at least $3n-2$ edges. Then $G$ cannot be drawn in the plane so that all crossings occur at the same point.
Proof. We make …
- 32.1k
17
votes
Applications of infinite graph theory
Here's a nice proof of the Cantor-Bernstein theorem in the language of infinite graphs.
Theorem. Let $G$ be an infinite graph with bipartition $(A,B)$. If $G$ has a matching saturating $A$ and a m …
- 32.1k