# Thread: Non-isophermic graphs

1. ## Non-isophermic graphs

Construct all non-isomorphic simple connected graphs on 8 vertices with 19 edges, at least one maximal degree vertex and at least one pendant vertex. Prove they are not isomorphicand that there are no more.

I ran out of ideas to do a graph with the conditions required in the question.

2. ## Graphs

Hello smithhall
Originally Posted by smithhall
Construct all non-isomorphic simple connected graphs on 8 vertices with 19 edges, at least one maximal degree vertex and at least one pendant vertex. Prove they are not isomorphicand that there are no more.

I ran out of ideas to do a graph with the conditions required in the question.
Here's a graph that satisfies the conditions to get you started. The vertices are $A_1...A_8$, with degree as follows:

$A_1:7$ (maximum)
$A_2:6$
$A_3:6$
$A_4:6$
$A_5:4$
$A_6:4$
$A_7:4$
$A_8:1$ (pendant)

The sum of the degrees of the vertices is 38, because there are 19 edges, each edge connecting 2 vertices.

To construct a second graph that's not isomorphic to this one, you could re-draw this one by removing the edge $(A_4, A_7)$ and replacing it by the edge $(A_5, A_6)$. This will produce the following specification:

$A_1:7$ (maximum)
$A_2:6$
$A_3:6$
$A_4:5$
$A_5:5$
$A_6:5$
$A_7:3$
$A_8:1$ (pendant)

I suspect there aren't many other possibilities.