[離散] - 圖論 2

1. Suppose G=(V,E) where V = {(1,3),(1,4),(1,6),(2,3),(2,5),(2,7),(3,7),(4,6),(4,7),(5,6)}

(d)Is G = ({1,2,4,5},{(1,4),(2,5),(5,6)}) a subgraph of G?
(e)Is the subgraph of G induced by {2,4,5,6,7} biconnected?

可以解釋一下嗎?


2.Suppose G=(V1,E1),H=(V2,E2) G,H is isomorphic,which of the statements are correct?
(a)|V1|=|V2| and |E1|=|E2|
(b)If G has Hamiltonian path, H has HP.
(c)If G is not planar,H isn't.
(d)If G has a matching of size k, H has,too
(e)G and H has same chromatic number.



4.Explain why every n-vertex srongly connected digraph contains at least n arcs

何謂arcs??