User gordon royle - MathOverflow

Answer by Gordon Royle for Let G be a graph such that for all u, v ∈ V (G), u no equal to v , |N (u) ∩ N (v )| is odd. Then show that the number of vertices in G is odd

2010-03-06T12:54:12Z

Jacob seems to have beaten me to it by a few minutes, but an algebraic graph theory proof works nicely, so I'll add my slight variant.

If $A$ is the $n \times n$ adjacency matrix of the graph, which we assume has no odd degree vertices, then over $Z_2$ the condition shows that $A^2$ has 0s on the diagonal and 1s elsewhere - i.e. that $A^2 = J - I$.

But (again over $Z_2$) $J-I$ has rank $n$ if $n$ is even. But $A$ does not have full rank as $A j = 0$ where $j$ is the all-ones vector (because graph has no odd degree vertices), and so neither can $A^2$.

Answer by Gordon Royle for Combinatorial results without known combinatorial proofs

2009-11-14T13:47:36Z

The number of (isomorphism classes of) self complementary graphs on n vertices is the difference between the number of graphs on n vertices with an odd number of edges and the number with an even number of edges.

This is relatively easy to prove with counting arguments, but I'd love to have a combinatorial proof of this...

Answer by Gordon Royle for What is the Tutte polynomial encoding?

2009-11-02T23:57:47Z

The real thing to focus on is the rank polynomial R(x,y) = T(x+1,y+1).

This is a generating function that counts the number of subsets of edges according to their size and their rank (where "rank" = "matroid rank" which in the graph case is equivalent to #edges - #components).

(Equivalently, you can view it as counting the numbers of subsets of edges according to their rank and their dual rank i.e. rank in the dual matroid.)

Tutte of course showed that the coefficients of the Tutte polynomial count spanning trees, but then you need to resort to ingenious artifice and introduce things like "numbers of internally active edges" and "numbers of externally active edges" to work out which coefficient each spanning tree is counted under.

In general working out which "graphical" properties are determined by this information - i.e. the numbers of subsets of edges of each size and rank - is non-trivial and so you shouldn't expect to just be able to "see" which properties are determined by the Tutte polynomial or not.

But there are some rules of thumb that the previous answerers have covered:

firstly, the TP depends on the cycle matroid of the graph and so anything that is non-matroidal will not be determined by the TP, which would include most things that involve "vertices" (such as degree sequence etc). [Just a warning though - there are some things whose natural definition uses vertices but that can through trickery be expressed in terms of edges only.]
secondly, one of the major results in the area is that the TP captures PRECISELY anything that can be computed by deletion/contraction, such as numbers of spanning trees, chromatic polynomial etc. This is a strong "if and only if" type statement in that a theorem called the "recipe theorem" shows that IF an invariant can be defined by deletion/contraction THEN it is an evaluation of the Tutte polynomial.

I think it is fair to say that MOST of the natural interpretations of the TP have by now been uncovered, but there are still occasional papers appearing that show that a given evaluation of the TP corresponds to a certain graphical invariant

Comment by Gordon Royle

2009-11-16T13:11:13Z

Yes, I wasn't really clear. The proof I know uses Polya theory and so you just set up the equations and the numbers magically come out the same on both sides. So it is just algebraic manipulation, rather than anything else. Therefore I'd like something bijective or at least a natural interpretation of this difference.