How many simple graphs on n vertices with vertex degrees all even?

문제출처

광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 3

Solution

1. Define the finite field
   Define the finite field $F_2$ (with elements 0 and 1). In $F_2$, addition follows modulo 2 arithmetic, meaning $1 + 1 = 0$.

2. Graph setup

   • The vertex set $V = \{v_1, v_2, \dots, v_n\}$ consists of $n$ vertices.
   • The edge set $E = \{e_1, e_2, \dots, e_m\}$ is the set of all possible edges. The number of edges is $m = \binom{n}{2}$, which represents all possible pairs of vertices.
   • Each edge is represented as $e = (i, j)$, where $i$ and $j$ are vertex indices. The presence of an edge between vertex $v_i$ and vertex $v_j$ is denoted by $x_{ij} \in F_2$. If $x_{ij} = 1$, then an edge exists; if $x_{ij} = 0$, no edge exists.
   • The degree of each vertex $v_i$, denoted $d(v_i)$, is defined as the sum of all edges connected to $v_i$. Using $x_{ij}$ ,where $x_{ij} = x_{ji}$, since this is an undirected graph, this is expressed as:
     $$
     d(v_i) = \sum_{j \neq i} x_{ij}.
     $$

3. Degree condition
   The degree of each vertex is even:
   $$
   d(v_i) \equiv 0 \pmod{2}.
   $$
   This condition ensures that the degree of each vertex is even, forming a system of linear equations over $F_2$ for each vertex $v_i$. There are $n$ such equations.

4. Construct the incidence matrix
   Construct the incidence matrix $M$ over $F_2$, where:

   • Rows correspond to vertices.
   • Columns correspond to edges.
   • The entry $M_{ik}$ is 1 if vertex $v_i$ is incident to edge $e_k$, and 0 otherwise.

   The system of equations from the degree condition can be expressed in matrix form:
   $$
   Mx = 0 \quad \text{(over $F_2$)},
   $$
   where $x$ is the vector of edge variables $x_{ij}$.

5. Solve the system
   Compute the dimension of the null space of $M$ to find the number of independent solutions. Using the rank-nullity theorem:
   $$
   \text{dim(null space of } M) = m - \text{rank}(M).
   $$

6. Rank of the incidence matrix
   If the graph is connected, the rank of $M$ is $n - 1$. Therefore, the dimension of the null space is:
   $$
   d = m - (n - 1) = \binom{n}{2} - (n - 1) = \frac{(n-1)(n-2)}{2}.
   $$

7. For disconnected graphs, the condition that all vertex degrees are even applies independently to each connected component. This does not change the final result.

8. Number of solutions
   The number of solutions, corresponding to graphs where all vertices have even degrees, is:
   $$
   2^d = 2^{\frac{(n-1)(n-2)}{2}}.
   $$
   Each free variable in the null space ,dimension $d$, can take two values ,0 or 1 in $F_2$, resulting in $2^d$ possible configurations.

주의

필드 설정, i,j 범위정의 등에서 감점요소가 있었습니다. addition, multipication도 정의가 필요합니다. field 대신 group으로의 정의도 고려해보세요. connect 라는 용어의 사용도 자제하는게 좋습니다. 최대한 자제하고 adjacent, incident로 명확하게 표현하는게 감점요인을 줄입니다.