Intereting Posts

Inequality understanding
Mathematical Telescoping
On the existence of a certain sequence of positive numbers
Are angles ever multiplied?
Differential Equation – $y'=|y|+1, y(0)=0$
Legendre Polynomials: proofs
Bob starts with \$20. Bob flips a coin. Heads = Win +\$1 Tails = Lose -\$1. Stops if he has \$0 or \$100. Probability he ends up with \$0?
The prime spectrum of a Dedekind Domain
Why is the number of possible subsequences $2^n$?
How often was the most frequent coupon chosen?
block matrix multiplication
Path-connected implies continuous?
Limit. $\lim_{n \to \infty}\frac{1^p+2^p+\ldots+n^{p}}{n^{p+1}}$.
$\left( \frac{1 \cdot 2}{p} \right) + \left( \frac{2 \cdot 3}{p} \right) + \cdots + \left( \frac{(p-2)(p-1)}{p} \right) = -1$
Expectation of the min of two independent random variables?

I am working through Trudeau’s Introduction to Graph Theory, which contains the following problem:

In the following table, the numbers in the second column are mostly even. If we ignore the first row on the ground that $v=1$ is such a trivial situation that its uniqueness is unremarkable, that leaves $v=4$ as the only number of vertices listed for which there are an odd number of graphs. Do you think this is due to chance, or can you think of some reason why $v=4$ should be unique?

v number of non-isomorphic graphs 1 1 2 2 3 4 4 11 5 34 6 156 7 1,044 8 12,346 9 308,708

Note, this problem concerns the number of *non-isomorphic* graphs.

- A partition of vertices of a graph
- Embedding Mazes - Spanning Trees of a Grid Graph
- Why do graph degree sequences always have at least one number repeated?
- Graph with 10 nodes and 26 edges must have at least 5 triangles
- Spanning Trees of the Complete Graph Avoiding a Given Tree
- Proving and Modeling Logical Consistence

Here’s what I have so far:

The maximum number of edges in a graph with $v=4$ is $\max(e)=\frac{1}{2}(v)(v-1)=\frac{1}{2}(4)(3)=6$. The graphs with $e=0,1,2,4,5,6$ come in pairs because each graph has a complement. So, there are an odd number of graphs with $v=4$ iff there are an odd number of graphs with $v=4$ and $e= \frac{\max(e)}{2}$.

There are 3 graphs with $v=4$ and $e= \frac{\max(e)}{2}=3$, so therefore there is an odd number of graphs with $v=4$.

However, I don’t understand why $v=4$ should be special in this regard, even though it feels special.

- Help with graph induction proof
- Generating a Eulerian circuit of a complete graph with constant memory
- counting full bipartite matchings
- prove that a graph is one-ended
- isomorphic planar graph with its complement
- Invariance of strategy-proof social choice function when peaks are made close from solution
- Tree having no vertex of degree 2 has more leaves than internal nodes
- Software for drawing and analyzing a graph?
- 3-regular graphs with no bridges
- Explicit bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves

**Definition**:

Let $g(n)$ denote the number of unlabeled graphs on $n$ vertices, let $e(n)$ denote its $2$-part, that is the largest power of $2$ which divides $g(n)$.

**Lemma**: If $n\geq5$ is odd then $e(n) = (n+1)/2-\lfloor \log_2(n) \rfloor$. If $n \geq 4$ is even then $e(n) \geq n/2 – \lfloor \log_2(n) \rfloor$ with equality **iff** $n$ is a power of $2$.

**Corollary**: The amount of unlabeled graphs is even for $n > 4$

Some values $e(\{4,5,\ldots,15\})=\{0,1,1,2,1,2,2,3,3,4,4,5\}$ (for even numbers it is the lower bound).

The theorem is due to Steven C. Cater and Robert W. Robinson and can be found, including a proof, in this publication.

They mention that $g(n)$ is not only even but contains a large number $2$’s in its prime factorisation for large $n$ (this also follows form the formula). In fact they even show that they are asymptotically $n/2$ factors of $2$ in $g(n)$.

If a graph on $n$ vertices has $e$ edges, then the number of edges in its complement is

$$

\frac{n(n-1)}{2} – e.

$$

So if if $n(n-1)/2$ is odd we can divide graphs in pairs (graph,complement),

and then the number of graphs must be even. In particular the the parity of the number of

isomorphism classes of graphs is equal to the parity of the number of isomorphism

classes of self-complementary graphs. When $n=4$, the path is the unique self-complementary graph and the number of isomorphism classes is odd.

Clearly when $n=6$ or $n=7$ there must be an even number of isomorphism classes self-complementary graphs.

- basic differential forms
- Bounded Linear Mappings of Banach Spaces
- prove a statement (complements of unions)
- Does infinity and zero really exist?
- Is this quotient Ring Isomorphic to the Complex Numbers
- Help finding the fundamental group of $S^2 \cup \{xyz=0\}$
- Is this space complete?
- $(a,b)$ homemorphic to $(c,d) \cup (h,k)$
- Deriving cost function using MLE :Why use log function?
- Integrating a product of exponentials and error functions
- why is a simple ring not semisimple?
- Two continuous functions that are the same in the rationals.
- Maximum likelihood estimate of hypergeometric distribution parameter
- Assume that $ 1a_1+2a_2+\cdots+na_n=1$, where the $a_j$ are real numbers.
- Define second derivative ($f''$) without using first derivative ($f'$)