0
$\begingroup$

If two homeomorphic graphs ($H_1$ and $H_2$) have $n_i$ vertices and $m_i$ edges, show that $m_1-n_1=m_2-n_2$

I know by the degree summ formula $\sum deg(v)=2E$

Proof:

Contract both graphs to the same graph $G$ with number of points $(k)$. Then, add vertices, such that the resulting graph becomes ($H_1$ and $H_2$).

For each vertex that we add, the number of edges increases by $1$ and the total degree increases by $2$.

Suppose we need to add $s$ points to $G$ to make it $H_1$ and $t$ points to $G$ to make $H_2$.

Then it follows that since $$\sum_{v\in G} deg(v)=2E$$

Since adding $s$ points contributes $2s$ to the total degree, similarly for $t$. I get: $$\sum_{s+v\in G} deg(v)=2E+s$$ Similarly for t:$$\sum_{t+v\in G} deg(v)=2E+t$$

Now I'm left to connect the total degree with the number of vertices.

$\endgroup$
1
$\begingroup$

Any graph is homeomorphic to a graph with no vertices of degree $2.$ In the process of removing a vertex of degree $2,$ you lose one vertex and one edge, so the difference $m-n$ is unchanged. Therefore, it suffices to show is that homeomorphic graphs with no vertices of degree $2$ are isomorphic (and so have the same number of vertices and the same number of edges). This is because, in the absence of vertices of degree $2,$ a homeomorphism between two graphs must take vertices to vertices and edges to edges.

$\endgroup$
1
$\begingroup$

The degree sum for the $H_1$ is $\sum_{s+v\in G} deg(v)=2E+2s$ and for $H_2$ is $\sum_{t+v\in H} deg(v)=2E+2t$. So number of edges are $E+s$ and $E+t$. I guess you can continue now to get the answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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