G is a underlying graph of an irregular multigraph

Theorem: Let $G$ be a connected graph of order 2 or more. Then $G$ is the underlying graph of an irregular multigraph (weighted graph) if and only if $G\neq K_2$

Not sure about proving the 'if' part of the theorem.

An idea is to begin with the connected graph $G$, the pick a degree that is repeated and choose an incident edge so that the other vertex on the edge has a different degree (do I need to prove there will always be such an incident edge?). Increase the weight of that edge until the degrees of both its end-vertices are not found in the whole graph.

Repeat the steps for all vertices that have degree same as another until we have an irregular weighted graph. So such an irregular multigraph (weighted) graph does exist.

If $M$ is a multigraph and all parallel edges between pairs of vertices are replaced by a single edge then the resulting graph is the 'underlying' graph of $M$

A weighted graph is another representation of a multigraph - instead of parallel edges, each edge has a "weight".

The algorithm you outline seems like it should work, more or less. You're right that the

choose an incident edge so that the other vertex on the edge has a different degree

step is concerning. It's less "you need to prove that you can always do this" and more "you can't always do this": if you're starting with a regular graph, you won't get anywhere!

But if your algorithm instead began "Pick two vertices with the same degree. Choose an edge of the graph that includes only one of them" and then proceeded as before, it would work. Prove that at every iteration, you're decreasing the number of pairs of vertices with the same degree. It follows that eventually the algorithm must terminate with no such pair of vertices.

Another approach is simply to number the edges of $G$ as $e_1, e_2, \dots, e_m$ and then set the weight of $e_i$ to $2^i$. If $G$ does not have a $K_2$ component, then the resulting graph will be an irregular multigraph.

• Thank you. For your alternative approach, how can one prove that the sum of any unique combination from the set $\{2^i\}$ produces a unique result? – Zeeshan Ahmad Nov 14 '17 at 0:19
• Every number has a unique binary representation! (If you're not willing to take that on faith, the sketch of a proof is as follows. You can't get a sum as large as $2^k$ using only the numbers $2^0, 2^1, \dots, 2^{k-1}$. So if two sums produce the same result, their largest terms must be equal. Remove those terms and repeat on the rest of both sums.) – Misha Lavrov Nov 14 '17 at 0:27