unit 5 dm

Question 1

When are two vertices said to be adjacent/neighbours?

Answer 1

one edge between them atleast pic8

Question 2

What is a null graph

Answer 2

no edges, all isolated vertexes

Question 3

What is a trivial graph?

Answer 3

no edges and one vertices

Question 4

What is a graph?

Answer 4

A collection of edges and vertices where the ordered pairs form edges

Question 5

What does Graph G(V,E) represent?

Answer 5

V is an unempty set of vertices and E is a set of ordered pairs which represent edges

Question 6

what does the therefore symbol represent (pic1)

Answer 6

null graph, 3 vertices

Question 7

How is an edge represented?

Answer 7

a line, straight, curvy, long or short

Question 8

Can the same graph be represented in diff ways? example?

Answer 8

pic2

Question 9

How can graphs be classified?

Answer 9

finite: finite no. of edges and vertices
infinite: infinite no. of vertices

Question 10

What are order and set and in which type of graph are the present?

Answer 10

In finite graph
OVSE
Order: no. of vertices
Set: no. of edges

Question 11

(n,m) graph?

Answer 11

order -> n

size -> m

Question 12

Graph(V,E) cardinality of V?

Set E cardinality?

Answer 12

|V| = order
|E| = size

Question 13

Null graph with n vertices representation?

Answer 13

(n,0) graph

Question 14

How are finite graphs classified?

Answer 14

1. Directed
   direction associated with edge (ordered pair)
2. Undirected
   no direction associated with edge (unordered pair)

Question 15

What are end vertices?

Answer 15

Vi and Vj are vertices joined by edge ek then edge vertices are Vi, Vj of ek
Symbolically pic3

Question 16

How are vertices and edges represented?

Answer 16

Vertices: V1, v2 (subscript)
OR
A,B,C…

Question 17

How are edges and edges represented?

Answer 17

e1, e2, e3..
or
AB, CD, …

Question 18

Can edges intersect and not form a vertex at intersection point

Answer 18

yes

pic5

Question 19

even if one vertix diff, denoted as

Answer 19

distinct end verticespic5

Question 20

self loop?

Answer 20

same vertex as end vertices

pic5

Question 21

loop?

Answer 21

edges with same end vertices
diff directions
pic5

Question 22

parallel edges

Answer 22

edges with same end vertices
same direction
pic5

Question 23

multiple edges

Answer 23

2 or more edges with same end vertix pic 4

Question 24

simple graph

Answer 24

no loops, no multiple edges

Question 25

loop free graph

Answer 25

no loops

Question 26

multigraph

Answer 26

no loops, yes multiple edges

Question 27

general graph

Answer 27

yes loops, yes multiple edges

Question 28

labeled graph

Answer 28

names are assigned to graph

Question 29

unlabeled graph

Answer 29

no names assigned to graph

Question 30

incidence

Answer 30

if there is an edge between A and B, A is incident on B pic 6 edge incident -> 2 vertices vertix incident -> as many vertices

Question 31

degree of vertices? in which graph type?

Answer 31

undirected | no. of vertices incident on a vertix (edges between how many vertices)

Question 32

adjacent edge

Answer 32

non parallel edges with one common vertix | pic7

Question 33

complete/full graph

Answer 33

order >= 2 (vertices) at least one edge between all vertices denoted by k subscript n (n = vertices) n = 5, Kuratowski's first graph pic9

Question 34

bipartite graph

Answer 34

pic10 split into 2 disjoint sets V1 and V2 every edge connects vertex from V1 to vertex in V2 None only within V1 or within V2

Question 35

complete bipartite

Answer 35

every v1 to every v2 | pic 11, kurotowskis second graph

Question 36

is complete bipartite, complete graph? why

Answer 36

no edge between same bipartite

Question 37

How to check if bipartite?

Answer 37

assign 2 colors alternatively no adj same color | pic 12

Question 38

Types of undirected simple graphs

Answer 38

complete cycle: every vertex degree = 2 pic13 wheel: vertex connected to every other vertex(all degree 3 except center = vertex no. - 1)pic14

Question 39

Types of graph

Answer 39

simple multi pseudo: self loops + maybe parallel edges pic15

Question 40

Directed graph G(V,E) u and v?

Answer 40

collection of ordered pairs V -> nonempty set of vertices E -> ordered set of edges starting ->u, ending -> v

Question 41

types of directed graphs

Answer 41

simple directed: no loops, no parallel edges multi directed: parallel edges pseudo/mixed directed: directed + undirected edges

Question 42

Union of graphs

Answer 42

G(V1,E1) union G(V2,E2) G(V,E) where V = v1 union V2 etc | pic 16

Question 43

path/walk

Answer 43

seq of edges/vertices

Question 44

circuit/closed walk

Answer 44

same initial and end point

Question 45

simple path

Answer 45

each edge only once

Question 46

adjacency and incidence

Answer 46

``` row,column = vertices row = vertices column = edges ```

Question 47

deg(V) or d(v)

Answer 47

no. of edges join V vertices, loops 2x

Question 48

degree sequence of graph

Answer 48

all degrees in non-ascending order

Question 49

degree of graph

Answer 49

min deg(V) of graph

Question 50

isolated vertex

Answer 50

not end vertix (deg(V) = 0)

Question 51

pendant vertex

Answer 51

deg(V) = 1

Question 52

pendant edge

Answer 52

edge from pendant vertex

Question 53

regular graph of degree k/k-regular graph

Answer 53

all vertices, same degree, k

Question 54

3 regular graph aka

Answer 54

cubic graph

Question 55

Peterson graph

Answer 55

pic17 | 10 vertices, 15 edges

Question 56

3d hypercube Q3

Answer 56

pic 18

Question 57

k regular grapgh, 2^k vertices aka

Answer 57

k dimensional hypercube Qk

Question 58

handshaking property why does it work? why called handshake? aka

Answer 58

``` sum of all degrees = 2 * edges each edge counted twice (at each end) even no. of hanshakes obvio First Theorem of Graph theory pic 19 -> math form ```

Question 59

Isomorphism

Answer 59

pic19 isomorphism reprsentation f:V->V' (f onto 1-1) {A,B}->E {f(A),f(B)}->E' SAME ADJ MATRIX(rearrange columns) SAME DEGREES Same order, same size -> not need isomorphic

Question 60

Subgraphs

Answer 60

g1 subgraph of g if: all vertices and edges of g1 in g edge in g1 same end vertices as g g1 part of g

Question 61

Subgraph results

Answer 61

all graphs subgraph of itself graph n vertices sub of complete kn single vertex in G1 sub G single edge + end verices sub G

Question 62

Spanning SubG

Answer 62

vertices in main

Question 63

Induced SubG

Answer 63

vertices and edges in main

Question 64

Edge/Vertex disjoint

Answer 64

both subs no common edge/no common edge and vertex | vertex disjoint -> edge disjoint

Question 65

complement of subG

Answer 65

G - subG(G1) = comp of G1 in G G - G1 or G1(bar) G1(bar) = G triangle G1

Question 66

walk classification

Answer 66

seq of vertixedge+ no. of edges -> length vertix and edge more than once possible

Question 67

how many paths of length n

Answer 67

A = adj matrix -> A^n paths