- #1
fishturtle1
- 394
- 82
- 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?
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?