Proving uniqueness of almost irregular graphs with equal degrees for n=2k

[fishturtle1]

Homework Statement

For every integer $n \ge 2$, there is exactly one graph of order $n$ containing a vertex of degree $n-1$ and containing exactly one pair of vertices having the same degree. What are these equal degrees?

Relevant Equations

A graph $G$ has order $n$ means it as exactly $n$ vertices.

A vertex $v$ has degree $k$ means it has $k$ edges connected to it.

A graph $G$ is almost irregular if it has exactly one pair of vertices the have the same degree.

I did the cases $n=2, 4, 6, 8$ by hand and got this far:
Answer: If $n = 2k$ for some integer $k$, the equal degrees is $k$.

Proof: Let $n \ge 2$ be an integer and consider two cases:

case1: $n = 2k$ for some integer $k$. Let $P(2l)$ be the assertion that for $2l \ge 2$ there exists exactly one graph of order $n$ that is almost irregular containing a vertex of order $n-1$ and exactly one pair of vertices having the same degree $l$. We proceed by induction.

base case: $n = 2\cdot1$. Let $G = (V, E)$ where $V = \lbrace v_1, v_2 \rbrace$ and $E = \lbrace v_1v_2 \rbrace$. The only other graph of order $2$ is $(V, \lbrace \rbrace)$. Thus, $G$ is the only graph of order 2 that satisfies the above properties (graph of order $2$ that is almost irregular containing a vertex of order $2-1$ and exactly one pair of vertices having the same degree $1$.). We may conclude $P(2)$ is true.

inductive step: Suppose $P(2k)$ is true for some integer $k$. We'll show this implies $P(2k+2)$. Since $P(2k)$ is true, there exists some unique graph $G = (V, E)$ of order $n$ with, say, vertices $v_1, v_2, v_i, v_j$ such that $\deg v_1 = 2k-1$ and $\deg v_2 = 1$, and $\deg v_i = k = \deg v_j$.

We'll construct a new graph $H = V_0, E_0$. Have $V_0 = V \cup \lbrace v_{2k+1}, v_{2k+2} \rbrace$. Let $E_0 = E \cup \lbrace v_{2k+1}v_x : x \neq 2, x \neq 2k+1 \rbrace \cup \lbrace v_{2k+2}v_1 \rbrace$. We have $\deg v_2 = 1$, $\deg v_{2k+2} = 2$, $\deg v_i = k + 1 = \deg v_j$, $\deg_{2k+2} = 2k$, and $\deg_1 = 2k+1$. Moreover, its clear(?) that for any integer $y \in \lbrace 1, 2, \dots, 2k+1 \rbrace$ there exists $z \in \lbrace 1, 2, \dots, 2k+1, 2k+2 \rbrace$ such that $\deg v_z = y$.

Thus, $H$ is a graph of order $2k+2$ that is almost irregular containing a vertex of order $2k+1$ and exactly one pair of vertices having the same degree $k$.

Next we need to show $H$ is unique. Let $H'$ be a graph of order $2k+2$ that is almost irregular containing a vertex of order $2k+1$ and exactly one pair of vertices having the same degree $k$. Then $H'$ has vertices $v_m, v_n$ such that $\deg v_m = 2k$ and $\deg v_n = 2$.
$\dots$

i'm not sure where to go from here, i was thinking we could remove specific two vertices from $H'$ and show we are back at $G$. Then we could argue that this implies $H' = H$. But I'm not sure which vertices these should be. Any hints, please.

I also put some "?"'s in the progress, because I'm not sure how to further justify these claims. How could i further justify these claims?

 

[andrewkirk]

For the proof by induction to work, you need a stronger induction hypothesis. Try this:

P(k) says that there exists a graph of order 2k that has two vertices of order k and one vertex of every other order from 1 to 2k-1 inclusive.

Our base case is for k=2, for which a solution is the 4-graph { {1 2} {1 3} {1 4} {3 4} } for which the orders of its vertices, from vertex 1 to vertex 4, are 3, 1, 2, 2.

For completeness, we also observe that the 2-graph {{1 2} } satisfies P(1), but it is easier to start the induction at k=2 because we then have four distinct points for the vertices of order 1, 2k, k and k.

Say P(k) is true, for k>=2. Label the vertices with orders 2k-1, 1, k and k as vertices 1, 2, 3, 4 respectively. The choice of which vertex of order k is labelled 3 is arbitrary and does not matter.

Then, applying your method for adding two new vertices, and using all the information in P(k), it can be shown without undue difficulty that in the augmented (2k+2)-graph, vertex 1 has order 2k+1, vertex 2 has order 1, vertex 2k+1 has order 2k, vertex 2k+2 has order 2, vertices 3 and 4 have order k+1 and the other vertices cover the orders 3, 4, ..., k, k+2, ..., 2k-1. Hence P(k+1) holds and the induction will be proved.

We can prove the same thing for odd-order graphs by defining hypothesis Q(k) to be that there exists a graph of order 2k+1 that has two vertices of order k and one vertex of every other order from 1 to 2k inclusive.

For k=0 the graph is the single point acyclic graph {}. For k=1 it is {{1 2} {2 3}}.
Our base case fir the induction is k=2, for which the graph is {{1 2} {1 3} {1 4} {1 5} {3 4} {4 5} }, for which vertex 1 has order 4, 2 has order 1, 4 has order 3 and vertices 3 and 5 have order 2.

The proof of the induction step is the same as for the even case.

See how you go in completing that proof, before trying to prove uniqueness.

 

[fishturtle1]

For the proof by induction to work, you need a stronger induction hypothesis. Try this:

P(k) says that there exists a graph of order 2k that has two vertices of order k and one vertex of every other order from 1 to 2k-1 inclusive.

Our base case is for k=2, for which a solution is the 4-graph { {1 2} {1 3} {1 4} {3 4} } for which the orders of its vertices, from vertex 1 to vertex 4, are 3, 1, 2, 2.

For completeness, we also observe that the 2-graph {{1 2} } satisfies P(1), but it is easier to start the induction at k=2 because we then have four distinct points for the vertices of order 1, 2k, k and k.

Say P(k) is true, for k>=2. Label the vertices with orders 2k-1, 1, k and k as vertices 1, 2, 3, 4 respectively. The choice of which vertex of order k is labelled 3 is arbitrary and does not matter.

Then, applying your method for adding two new vertices, and using all the information in P(k), it can be shown without undue difficulty that in the augmented (2k+2)-graph, vertex 1 has order 2k+1, vertex 2 has order 1, vertex 2k+1 has order 2k, vertex 2k+2 has order 2, vertices 3 and 4 have order k+1 and the other vertices cover the orders 3, 4, ..., k, k+2, ..., 2k-1. Hence P(k+1) holds and the induction will be proved.

We can prove the same thing for odd-order graphs by defining hypothesis Q(k) to be that there exists a graph of order 2k+1 that has two vertices of order k and one vertex of every other order from 1 to 2k inclusive.

For k=0 the graph is the single point acyclic graph {}. For k=1 it is {{1 2} {2 3}}.
Our base case fir the induction is k=2, for which the graph is {{1 2} {1 3} {1 4} {1 5} {3 4} {4 5} }, for which vertex 1 has order 4, 2 has order 1, 4 has order 3 and vertices 3 and 5 have order 2.

The proof of the induction step is the same as for the even case.

See how you go in completing that proof, before trying to prove uniqueness.

Thanks for the reply! Here's (I think) an induction proof for existence:

Proof: Let $P(k)$ say that there exists a graph $G$ of order $2k$ that has exactly two vertices of degree $k$ and exactly one vertex of degree $x$ for $x \in \lbrace 1, 2, \dots , k-1, k+1, \dots 2k-1\rbrace$.

base case: Observe the 4-graph { {1 2} {1 3} {1 4} {2 3} } for which the orders of its vertices, from vertex 1 to vertex 4 are 3, 2, 2, 1, satisfies $P(2)$.

For completeness $P(1)$ is satisfied by { {12} }, however, the induction is easier to start at $k=2$ since there are four distinct points with order $1, k, 2k-1$.

inductive step: Suppose $P(k)$ is true for some $k \ge 2$. Then there exists a graph $G = (V, E)$ that satisfies $P(k)$. We label the vertices of $G$ such that $\deg v_1 = 2k-1, \deg v_2 = 1, \deg v_3 = k = \deg v_4$.

Next, define $V_1 = \lbrace v_{2k+1}, v_{2k+2} \rbrace, E_1 = \lbrace v_{2k+1}v_i : v_i \neq v_2, v_i \neq v_{2k+1} \rbrace, E_2 = \lbrace v_1v_{2k+2} \rbrace$. We can then define a new graph $H = \lbrace V \cup V_1, E \cup E_1 \cup E_2 \rbrace$. Clearly, $H$ has order $2(k+1)$. Moreover, $\deg v_1 = 2k+1, \deg v_2 = 1, \deg v_3 = k+1 = \deg v_4, \deg v_{2k+1} = 2k, \deg v_{2k+2} = 2$. Lastly, for $x \in \lbrace 2, 3, \dots , k-1, k+1, \dots 2k-2 \rbrace$, by $P(k)$, there exists a unique vertex $v_j$ ( where $v_j \neq v_1, v_2, v_3, v_4$) such that in our original graph $G$, we have $\deg v_j = x$. Thus, for $x+1 \in \lbrace 3, 4, \dots, k, k+2, \dots, 2k-1 \rbrace$, there exists a unique $v_j$ in $H$, such that $\deg v_j = x+1$.

Thus, $P(k+1)$ is satisfied by $H$. By induction, we may conclude $P(k)$ is true for $k \ge 1$.

Next, let $Q(k)$ sat that there exists a graph of order $2k+1$ with exactly two vertices of order $k$ and exactly one vertex with order $x$ for $x \in \lbrace 1, 2, \dots , k-1, k+1, \dots, 2k \rbrace$.

base case: Consider the 5-graph { {12} {13} {14} {15} {24} {45} }. Observe that the degree of vertex 1 to vertex 5 is 4, 2, 1, 3, 2. Thus, $Q(2)$ is satisfied. For completeness, observe that { {12} {13} } satisfies $Q(1)$. We start the induction at $k = 2$ because it is helpful to have four distinct vertices with degree $1, k, 2k$.

inductive step: Suppose $Q(k)$ is true for some $k \ge 2$. Let $G = (V, E)$ be a graph that satisfies $Q(k)$. We label the vertices of $G$ such that $\deg v_1 = 2k, \deg v_2 = 1, \deg v_3 = k = \deg v_4$.

Let $V_1 = \lbrace v_{2k+2}, v_{2k+3} \rbrace, E_1 = \lbrace v_{2k+2}v_i : v_i \neq v_2, v_i \neq v_{2k+2} \rbrace, E_2 = \lbrace v_1v_{2k+3} \rbrace$. We then define a new graph $H = \lbrace V \cup V_1, E \cup E_1, \cup E_2 \rbrace$. Clearly, $H$ has order $2k+3$. Also, $\deg v_1 = 2k+2, \deg v_2 = 1, \deg v_3 = k+1 = \deg v_4, \deg v_{2k+2} = 2k+1, \deg v_{2k+3} = 2$. Finally, since $P(k)$ is true, we have in our original graph G, if $x \in \lbrace 2, 3, \dots, k-1, k+1, \dots 2k-1 \rbrace$ then there exists a unique $v_j$( where $v_j \neq v_1, v_2, v_3, v_4$) such that $\deg v_j = x$. Therefore in our new graph $H$, for $x+1 \in \lbrace 3, 4, \dots k, k+2, \dots, 2k \rbrace$, there is a unique $v_j$ such that $\deg v_j = x + 1$.

Thus, $H$ satisfies $Q(k+1)$. By induction, we may conclude $Q(k)$ is true for $k \ge 1$. []

 

[fishturtle1]

I think this will help prove uniqueness. The book gives the following theorem and a strategy to prove it... i try to fill in the details..

Theorem 2.2: For each integer $n \ge 2$, there are exactly two almost irregular graphs of order $n$, and they are complements of each other.

Proof: Let $R(k)$ say that for $k \ge 2$, there are exactly two irregular graphs of order $k$, and they are complements of each other.

base case: There are exactly two graphs of order $2$: $G_2 = \lbrace \lbrace 1 2 \rbrace \rbrace$ and $H = \lbrace \rbrace$. Observe that, in $G_2$, $\deg v_1 = 1 = \deg v_2$. Moreover, if $i \neq j$ and $i, j \neq 1, 2$ then $\deg v_i \neq \deg v_j$ and $\deg v_i, \deg v_j \neq 1$. Thus $G_2$ is almost irregular. By similar reasoning $H_2$ is almost irregular. Lastly, its clear that $G_2$ and $H_2$ are complements of each other. Thus, $R(2)$ is satisfied.

ind. step: Suppose $R(k)$ is true for some $k \ge 2$. Let $G_k, H_k$ be the graphs that satisfy $R(k)$, where $G_k$ has a vertex of degree $0$ and $H_k$ has a vertex of degree $k-1$. Note that this must be the case, since for $k \ge 2$, an almost irregular graph of order $k$ must have either a vertex of degree $0$ or degree $k-1$. Moreover, a graph of order $k$ clearly can't have both a vertex of degree $0$ and a vertex of degree $k-1$.

Consider adding a vertex of degree 0 to $H_k$. This new graph, call it $G_{k+1}$ is an almost irregular graph of order $k+1$ with a vertex of degree $0$. Its complement, call it $H_{k+1}$ is an almost irregular graph of order $k+1$ with a vertex of degree $k$.

We've shown existence. Next, we show uniqueness.

Suppose $H_{k+1}$ and $A$ are two almost irregular graphs of order $k+1$, each with a vertex of order $k$. We can remove this vertex of order $k$ and all edges incident to it, thereby decreasing the degree of the remaining vertices by $1$. For both graphs $H_{k+1}$ and $A$, the resulting graph is $G_k$. It follows $H_{k+1} = A$.

Suppose $G_{k+1}$ and $B$ are two almost irregular graphs of order $k+1$, each with a vertex of order $0$. We can remove this vertex, which leaves every other vertex's degree unaffected. The resulting graph, for both $G_{k+1}$ and $B$, is $H_k$. It follows $G_{k+1} = B$.

We may conclude there are exactly two almost irregular graphs of order $k+1$: $G_{k+1}$ and $H_{k+1}$. Moreover, the complement of $G_{k+1}$ is an almost irregular graph with a vertex of order $k$. But we've just shown that this must be the graph $H_{k+1}$. Thus, $G_{k+1}$ and $H_{k+1}$ are complements of each other.

Thus, $R(k+1)$ is true. By induction, $R(k)$ is true for all $k \ge 2$. []

Back to the original problem: We've shown there is exactly one almost irregular graph of order $k$ with a vertex of order $k-1$, for $k \ge 2$. Combining this with post #3, we may conclude the original statement which is: For $n \ge 2$, there is exactly one graph of order $n$ containing a vertex of degree $n-1$ and exactly one pair of vertices of equal degree. We may write $n$ as either $n = 2k$ or $n = 2k+1$ for some integer $k$. In this case, the equal degree is $k$. []