Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ??

share|improve this question
1  
What is it you're having trouble proving? –  Qiaochu Yuan Nov 22 '10 at 23:57
add comment

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
@ALbin: Yes, you are right. –  Aryabhata Nov 24 '10 at 19:23
    
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.) $ –  Albin. Com. Nov 24 '10 at 19:30
add comment

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.

share|improve this answer
    
+1: Nice construction! –  Aryabhata Nov 23 '10 at 1:17
    
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} $$. –  Albin. Com. Nov 23 '10 at 15:30
    
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 $$ –  Albin. Com. Nov 23 '10 at 15:30
    
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" –  Albin. Com. Nov 23 '10 at 19:07
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.