Graph and Tree

Question 1

Undirected graphs

Answer 1

Two vertices u and v in graph G are call neighbours in G if u and v are endpoints of an edge e of G. e connect u and v

Question 2

Degree of vertex

Answer 2

The number of edges that incident with it

deg(v)

deg(v)=0 is called isolated
A vertex is pendant iff has a deg of one

Question 3

Σdeg(v)=2e

Answer 3

Σdeg(v)=2e

Question 4

An undirected graph has an even number of vertices of odd degree

Answer 4

An undirected graph has an even number of vertices of odd degree

Question 5

IN and OUT degree

Answer 5

in-degree of a vertex v,
denoted by deg-(v)

Out-degree of a vertex v,
denoted by deg+(v)

Question 6

Let G=(V,E) be a graph with directed edges

Answer 6

Σdeg-=Σdeg+=|E|

Question 7

Graph Kn

Answer 7

Question 8

Cycle

Answer 8

has at least 3 vertices

Question 9

The wheels

Answer 9

Question 10

The cube

Answer 10

Question 11

Bipartite Graph

Answer 11

Given two non-empty set of vertices
and in graph G
V1 and V2

V1^V2=0/
V1vV2=G

Question 12

Induced subgraph

Question 13

Graph isomorphism

Answer 13

The simple G1=(V1,E1) and G2(V2,E2) if there exists one to one and onto function

Question 14

A path vs a cycle

Answer 14

Path visits all the vertices exactly once but doesn’t have to start and ends at the vertex

Cycle is the same thing but starts and ends at the same vertex

Question 15

Euler cycle

Answer 15

Must be a connected graph
Must start and ends at the same vertex
Visit each edge once
At least 2 vertices has even degree

Question 16

Euler path

Answer 16

Must be a connected graph
Visit each edge once
Must have exactly 2 vertices with odd degree

Question 17

Hamilton Path

Answer 17

A simple path in graph G passes through every vertex exactly once

Question 18

Hamilton cycle

Answer 18

A simple cycle in graph G passes through every vertex exactly once

Question 19

If G=(V,E) is a graph with Hamiltonian cycle, then G-v is connected for every vertex vCV

Question 20

Let G=(V, E) be a bipartite graph with by partition V=V1vV2

Answer 20

If G has a hamiltonian cycle the |V1|=|V2|

Question 21

If deg(x)+deg(y)>=n-1 for all x,y CV with x/=y

Answer 21

Then G has a hamiltonian path

Question 22

Planar graph

Answer 22

if it can be drawn in the plane without any edges crossing.

Question 23

Euler’s formula for planar

Answer 23

V-E+F=2

Question 24

Σdeg(fi)=2|E|

Answer 24

Σdeg(fi)=2|E|

Question 25

If G is a connected planar graph

Answer 25

has the max number of edges

e≤3v-6

Question 26

If G is a connected planar simple graph with V≥3 and no circuit length 3

Answer 26

then e≤2v-4

Question 27

DUal graph

Answer 27

in embedded planar graph, and has vertices in the middle of the face and connect with the same edges as the og

Question 28

The 5 platonic solid

Answer 28

Question 29

Tree

Answer 29

G is a tree if G is connected and does not contain a cycle

Question 30

Forest

Answer 30

G is a forest if G does not contain a cycle (every component of a forest is a tree)

Question 31

a leaf or pendant vertex

Answer 31

A vertex of deg 1

Question 32

If T=(V, E) is a tree with leaf v the T-v is a tree

Answer 32

If T=(V, E) is a tree with leaf v the T-v is a tree

Question 33

If T=(V, E) is a tree and u, v∈ V are distinct, there is a unique path in T with ends u,v

Answer 33

If T=(V, E) is a tree and u, v∈ V are distinct, there is a unique path in T with ends u,v

Question 34

Main properties of tree

Answer 34

If T= (V, E) is a tree the |V|=|E|+1
If G=(V,E) is a forest with K trees then |V|=|E|+K

Question 35

If G=(V, E) satisfies|V|=|E|+1 then G must have a vertex of deg 0 or at least two degrees of 1

Answer 35

If G=(V, E) satisfies|V|=|E|+1 then G must have a vertex of deg 0 or at least two degrees of 1

Question 36

Properties of trees

Answer 36

A tree with n vertices has n-1

Question 37

Rooted tree T=(V, E) is a tree with a distinguished vertex called the root

Answer 37

Rooted tree T=(V, E) is a tree with a distinguished vertex called the root

the root is a unique vertex at level 0

Question 38

Rooted tree terminology

Answer 38

The height is the number of a rooted tree is the max level of the vertex

Parent, Child

Ancestor and descandent

Question 39

Subtree

Answer 39

Question 40

Isomorphic of tree

Answer 40

Bijection

1) {f(u),f(v)} ∈E <==>{u,v} ∈E
2. f send the root of T1 to the root of T2

Question 41

M-ary

Answer 41

is the tree with m children

binary means some vertices have 2 children
3-ary means some has 3 children

Question 42

Pre-order traversal

Answer 42

Visit root then visit subtree from left to right

Question 43

Post-Order traversal

Answer 43

Visit subtrees left to right then visit root

Question 44

Spanning tree

Answer 44

Let G be a connected multigraph. A subgraph T of G is a spanning tree if T spans G

IN order to find spanning subgraph

it has no cycle
must span 3