7
$\begingroup$

In a few examples i noted that the existence of $k$-regular graph on n vertices is :

  1. True , for k or n even.
  2. False , for k and n odd . But we can find a graph with $n-1$ vertices with degree k and one vertex with degree $k-1$. There doesn't exists a k-regular graph for k and n odd because $k=\deg(G) = 2*|E(G)| / |V(G)|$ $|E(G)| = k*n/2$, and $|E(G)|= m$ is not a natural number if $n$ and $k$ is odd.

Any proof idea ??

  • 1
    What is it you're having trouble proving?2010-11-22

3 Answers 3

2

A lot easier way: the sum of the degrees is 2|E|. Therefore the sum of the degrees must be an even number. Since an odd times an odd is always an odd, and the sum of the degrees of an k-regular graph is k*n, n and k cannot both be odd.

7

At the outset, you should assume that $k < n$.

If $n = 2m$ is even, construct a graph with vertex set $$ \{ X_i : i \in \mathbb{Z}_m \} \cup \{ Y_i : i \in \mathbb{Z}_m \}, $$ where $\mathbb{Z}_m$ is the integers modulo $m$. Connect $X_i$ to $Y_j$ if $j-i \in \{1,\ldots,k\}$, where subtraction is done modulo $m$. Each $X_i$ is connected to $Y_{i+1},\ldots,Y_{i+k}$, and each $Y_j$ is connected to $Y_{j-1},\ldots,Y_{j-k}$.

If $k = 2l$ is even, construct a graph with vertex set $$\{X_i : i \in \mathbb{Z}_n\}.$$ Connect $X_i$ and $X_j$ if $i \neq j$ and $i-j \in \{-l,\ldots,l\}$. This relation is symmetric (since $j-i = -(i-j)$), and every $X_i$ is connected to $X_{i-l},\ldots,X_{i+l}$.

As you mentioned, when both $n,k$ are odd, we have $2e = nk$ where $e$ is the number of edges (this formula is obtained by counting all endpoints of all edges), which is a contradiction.

  • 0
    The real point is that i must find ex(n, H) , where ex(n,H) is the minimum value such that every graph G on n vertices with |E(G)| ≥ ex(n, H) contains H as a subgraph, and H is the star $ H_{1,r} $. The maximum degree of such G Δ <= r-1.So, using the avarage degree if I find a r-1 regular graph on n vertices all done : $$ ex(n,H_{1,r}) = \frac{ \lvert V(G) \rvert * (r-1) } {2} $$.2010-11-23
  • 0
    But i saw that anyway we can construct a graph strictly similar to r-1 regular: If n and k = r-1 is odd , we can construct a graph with |V(G)| - 1 vertices at degree k (r-1) and one to degree k-1 (r-2). So in that case $$\{ ex(n,H_{1,r}) = \lfloor \frac{ \lvert V(G) \rvert * (r-1) } {2} \rfloor $$2010-11-23
  • 0
    For n=2m that's not work if k > m: Because every vertex must have degree k > m and the edges are defined between two set { $ X_i:i∈Z_m $ } and { $ Y_i:i∈Z_m $} of both size m. "If i don't miss understood"2010-11-23
5

There is a theorem (Erdos-Gallai) on degree sequences:

$\displaystyle d_i$ is a degree sequence of some graph if and only if

$\displaystyle \sum_{i=1}^{m} d_i \leq m(m-1) + \sum_{i=m+1}^{n} \min \{d_i, m\} \ \ \text{for} \ \ m \in \{1,2, \dots, n\}$

and

$\displaystyle \sum_{i=1}^{n} d_i$ is even.

It should be easy to verify for the case when $\displaystyle d_i = k \ \ \forall i \in \{1,2, \dots, n\}$ (cumbersome verification at the end of the answer).


The case $\displaystyle k=n-1$, we trivially know the existence of a regular graph ($\displaystyle K_n$).

Suppose $\displaystyle k \lt n-1$.

Now for $\displaystyle 1 \le m \le k$ we have that

$\displaystyle m(m-1) + (k-m)m + (n-k)k -mk = nk - k^2 - m \ge nk-k^2 - k = k(n-k-1) > 0$

For $\displaystyle m \gt k$ we have

$\displaystyle m(m-1) + (n-m)k - mk = m^2 - m(2k+1) + nk = (m-(2k+1)/2)^2 +nk - ((2k+1)/2)^2$

For $k \lt n-1$ we have that $\displaystyle 4nk \gt 4k^2 + 4k$

i.e. $4nk \ge 4k^2 + 4k + 1 = (2k+1)^2$.

Hence $\displaystyle m(m-1) + (n-m)k - mk \ge 0$

Thus if $\displaystyle kn$ is even, there exists a $k$-regular graph on n vertices.

The other part I leave to you.

  • 0
    @ALbin: Yes, you are right.2010-11-24
  • 0
    Great proof !! But i don't get it for $ \displaystyle 1 \le m \le k $ . For me, it is : for $ \displaystyle 1 \le m \le k $ we have that : $$$$ $ \displaystyle m(m-1) + (n-m)m \ge mk $ ( for $ \displaystyle 1 \le m \le k $ we have $ min\{d_i=k,m\}=m $ ) $$$$ $ \displaystyle m-1 + n-m \ge k $ $$$$ $ \displaystyle n-1 \ge k $ (that is true.) $2010-11-24