# MIDTERM exercise

###### tags: `MIDTERM`

1. ### Prove that $G \cong H$ iff $\bar G \cong \bar H$ by the definition of isomorphism.

use adjacency matrix 0->1  1->0

2. ### Draw a Petersen graph with labeled vertices and what is the girth of the Petesen

[2020-03-27 Petersen Graph](https://hackmd.io/Q7zr3d6mQVmRv2VtWxrtcQ?both#P6-Petersen-Graph)
* girth(周長): A graph with a cycle is the length of its shortest cycle.

3. ### Show the maximum degree and the number of the components of $G+H$ where $G,H$ are two given graphs.

(Hint: Because $G,H$ are given, you can defined the parameters of those two graphs to help you show the answers.)

sol.
G的component有g個，H的component有h個，所以G+H的component有g+h個

max_degree = $Max(D(G),D(H))$

4. ### Prove that if $v \in V(G)$ has the degree at least two, then graph G has a cycle.
[2020-04-10 Fundamental Concept III P.30](https://hackmd.io/QIz8EtcKRqWANklnF4S-Fw?both#P30)

    select endpoint of a path

5. 沒有第5題
6. Draw the adjacency matrix and the incidence matrix of following graph

7. Prove or disprove: If $G$ is a simple graph which has no isolated vertex and no
induced subgraph with exactly two edges, then G is a complete graph

2. Prove that every graph with diameter $d$ has an independent set with at least $\lceil \frac{1+d}{2} \rceil$

diameter d: 
考慮 path of d

Determine the connectivity in Petersen Graph.

## Extra


>[color=#FF00FF]
>[name=Neko]

>[color=#00a000]
>
>endpoints
>[name=Omnom]

>[color=#FF00FF]sol
>
>[name=Neko]

>[color=#FF00FF]1.2.
>[name=Neko]

$K_{m.n}$
m, n are not both odd.


>[color=#FF00FF]sol
>
>
>
>
>[name=Neko]

>[color=#FF00FF]sol
>
>[name=Neko]

>[color=#FF00FF]sol
>
>[name=Neko]

>[color=#FF00FF]sol
>
>[name=Neko]