MIDTERM exercise

tags: MIDTERM

1. Prove that

   $G\cong H$ iff

   $\overline{G}\cong \overline{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

   • 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

   ​​​​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

8. 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

Neko

endpoints
Omnom

sol

Neko

1.

2.

Neko

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

sol

Neko

sol

Neko

sol

Neko

sol

Neko