graph theoryproof-writing
Using the Pigeonhole Principle, prove that in any graph with two or more vertices there must exist two vertices that have the same degree. (Note: the problem does not assume that the graph is connected. Your proof must work for any graph, even those in which some vertices are isolated.)
I don't have any idea how to do this. Any advice?
You can do it by induction, but the induction skips a size, so you’ll need to check two consecutive base cases.
Suppose that you have a bipartite graph $G_n$ with vertex classes $V_0$ and $V_1$, each containing $n$ vertices, one of each degree from $1$ through $n$. Add an isolated vertex to each part to get a bipartite graph $H_n$, each of whose parts contains one vertex of degree $k$ for $k=0,\dots,n$. Now add one more vertex to each part, connecting it by an edge to each vertex in the other part. The resulting graph $G_{n+2}$ will be bipartite, and each part will contain one vertex of degree $k$ for $k=1,\dots,n+2$.
You seem to be proving the wrong result. In this setting, there are two cases:
All odd-degree vertices belong to the same connected component. In this case, there is, by definition, a path from any odd-degree vertex to any other odd-degree vertex.
Two odd degree vertices belong to disjoint components. In this case, there are, by definition, two odd-degree vertices for which there is no path connecting them. And this situation can occur: just take the disjoint union of any two graphs each with an odd degree vertex.
For example, there is no path connecting the two pink vertices below:
This means you're either attempting to prove something that is true by definition, or you're attempting to prove something that is false.
I suspect the correct task is to prove:
Given a connected graph with exactly two odd-degree vertices $u$ and $v$, there is an Eulerian trail from $u$ to $v$.
Since I have been asked to "Please take care in reading my proof.":
WLOG we can assume if k is odd then the graph is not connected.
Here's a connected $5$-vertex graph counterexample:
Then the graph has at least one connected component.
All graphs with at least $1$ vertex have at least one connected component.
For any k=n the endpoints of these connected components have degree 1.
Many graphs don't have "endpoints", i.e., leaf vertices (such as the one below).
If the graph is connected and has an even number of vertices then the vertices have degree (n-1), which is odd.
Here's a counterexample to this claim:
In fact, any connected subgraph of $K_n$, except $K_n$ itself, would be a counterexample.
Best Answer
Suppose we have $n$ vertex and $\deg(v_i)$ denotes the degree of vertex. Notice that $\deg(v_i)\in \{0,1,\ldots,n-1\}$.
Now, Assume not,
That means that $\deg(v_i)$ is one to one function from vertex set to $\{0,1,\ldots,n-1\}$ since both of them have $n$ element then it must be also onto.
There exist $i,j$ such that $\deg(v_i)=0$ and $\deg(v_j)=n-1$ which is a contradiction. Since if one vertex has no connection the other vertex has at most $n-2$ connections.