0
votes
0answers
25 views

Maximum size of a poset chain

Let m,n ≥ 2. Consider the poset ({1,...,m}×{1,...,n}, ρ) where ρ is defined by (i,j)ρ(k,l) if and only if i ≤ k and j ≤ l. What is the maximum size of a chain in this poset? What is the maximum size ...
0
votes
0answers
38 views

Thickness of G when G is a simple connected graph

The thickness of a simple graph G is the smallest number of planar subgraphs of G that have G as their union. Show that if G is a connected simple graph with v vertices and e edges, where v ≥ 3, then ...
1
vote
1answer
21 views

Eulerian connected graph [on hold]

I have a question on grap theory as follows $G=(V,E)$ is a connected graph. Prove that G is Eulerian if and only if there is a partition $E_j$, $j=1,...,m$ of the set of edges such that every $E_j$ ...
0
votes
0answers
23 views

prove splits compatible if and only if edge-split

"Prove that if $e_A$ and $e_B$ are distinct edges of a binary $X$-tree $T$ and $C=A\Delta B$(symmetric difference), then the splits $\sigma(A), \sigma(B)$ and $\sigma(C)$ are compatible if and only if ...
0
votes
1answer
19 views

Draw all of the nonisomorphic simple graphs which have 5 vertices and 6 edges. [on hold]

How to draw nonisomorphic simple graphs which have 5 vertices and 6 edges? Can you guys please show me how to draw that with an explanation, help will be appreciated. Thanks
0
votes
2answers
20 views

drawing non-isomorphic graphs

I do understand that isomorphic means that they must have the same edges, vertices and adjacency must preserve. Can anyone please just draw a simple example with an explanation. Thanks
0
votes
3answers
29 views

Planar Graph max min edges

Consider a planar graph with 5 vertices, what is the minimum and the maximum number of edges such a graph can have? The graph need not be connected and is simple.
0
votes
1answer
26 views

How to deduce that $K_{m,n}$ is hamiltonian iff $m = n\ge 2$

I know how to prove that a bipartite graph $G$ with bipartitions $B$ and $W$ must both have the same number of vertices. I am having trouble, though, proving that they must have at least 2 vertices. ...
0
votes
2answers
96 views

Every planar graph has a vertex of degree at most 5.

I am trying to prove the following statement, any help!? Prove that every planar graph has a vertex of degree at most 5.
0
votes
1answer
55 views

n-dimension hypercube!

An $n$-dimension hypercube $f(n)$ is defined as follows. Basis Step: $f(1)$ is a graph with $2$ vertices connected by a link, and with $1$-bit ID for each vertex. Recursive step: To define $f(n)$ for ...
0
votes
3answers
85 views

N-Dimension Hypercube question? (making sense of the question)

I just failed a test in discrete math. Here is the Question that cost me the most points: An n-dimension hypercube f(n) is defined as follows. Basis Step: f(1) is a graph with 2 vertices ...
-1
votes
1answer
89 views

Cut Edges Question [on hold]

I am having somewhat difficulty proving this: Show that every graph has an edge cut $[S, V \setminus S]$ such that $|[S, V \setminus S]| \geq \dfrac{|E(G)|}{2}$. Thank you for your time!
-3
votes
3answers
55 views

Graph Theory - Proof - Isomorphism [on hold]

If anyone can help me prove the following: Suppose that $G$ is a plane graph which is isomorphic to its dual. Prove that $G$ has $2n-2$ edges. I thank you for your time!
2
votes
1answer
35 views

Smallest Graph that is Regular but not Vertex-Transitive?

I'm trying to find the smallest graph that is regular but not vertex-transitive, where by smallest I mean "least number of vertices", and if two graphs have the same number of vertices, then the ...
0
votes
1answer
24 views

Why does a 2-colourable simple graph with n nodes have no more than $(n^2/4)$ arcs?

Why does a 2-colourable simple graph with n nodes have no more than $(n^2/4)$ arcs? I would really appreciate for any kind of explanations.
-2
votes
0answers
51 views

Graph Theory - Lower bounds [on hold]

I am trying to solve for the following problem: Find (and justify) a lower bound for 0(G) in terms of X'(G) and E|(G)| and alpha'(G). (where alpha'(G) represents the maximum size of a matching in ...
0
votes
0answers
48 views

Number of edges of a plane graph isomorphic to its dual [on hold]

I am having trouble proving the following statement: Suppose that $G$ is a plane graph which is isomorphic to its dual. Prove that $G$ has $2n-2$ edges.
1
vote
2answers
62 views

Graph Theory - Proof

I am need help to Prove the following statement: Let G be a $k$-regular graph with $n$ vertices and $k \geq 1$. Prove that $G$ does not have an independent set of size greater than $\dfrac{n}{2}$. ...
0
votes
1answer
70 views

Graph Theory - Complete graphs [on hold]

I am having trouble with this question... Find the expected number of copies of $k_k$ in $G(n,1/2)$. Can anyone help!?
1
vote
2answers
59 views

Chromatic polynomial of a graph - might take a while

I'm currently struggling with graphs that require either adding edges, or removing them. Problem here being that the graphs I'm working on takes forever to complete and I don't really know if adding ...
9
votes
1answer
83 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
2
votes
1answer
53 views

Confusion regarding steps in bipartite matching proof

Can someone please explain how it follows that $|N(S)|x \geq |S|x$? What I'm asking is why is it necessary to use the value of x to derive the inequality? Theorem 5.2.7. Let G be a bipartite graph ...
0
votes
1answer
37 views

Determining the total degree of a tree

At the start of the solution, I understand that any tree with four vertices has three edges. I don't understand the next statement: "Thus the total degree of a tree with four vertices must be 6." ...
0
votes
1answer
28 views

Chromatic Equivalence Requirements

I have searched and searched and am unable to find the answer that I am looking for. I am trying to determine the conditions required for two graphs to have the same chromatic polynomial. On both ...
1
vote
2answers
40 views

What is the difference between a simple graph and a complete graph?

I might be having a brain fart here but from these two definitions, I actually can't tell the difference between a complete graph and a simple graph.
0
votes
1answer
13 views

Discrete math on multipartite graph

I am wonder about these problem 1.The complete Multi-partite graph $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$ 2.the number of edge of $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$
-1
votes
1answer
28 views

How many different binary search trees can be made with three pieces of data? [closed]

This is for a discrete math course, not computer science.
0
votes
2answers
35 views

I'm not quite sure I understand my book's reasoning for the answer

I have the following homework problem: Does there exist a graph, $G$, with 28 edges and 12 vertices, each of degree 3 or 4? First, my solution. $$ \sum deg(v_i) = 2 \cdot |E| \\ |E| = 28 ...
0
votes
1answer
37 views

How do I construct a minimum spanning forest?

I realize that a minimum spanning forest in a weighted graph is a spanning forest with minimal weight. Does this mean that I construct it by turning all of the trees into spanning trees?
1
vote
1answer
41 views

What is the difference between a forest and a spanning forest?

If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree). If a graph is ...
0
votes
0answers
20 views

probability in graphs - degree distribution

I am reading this paper on networks which employs probability in analyzing graphs. Suppose that a graph has $n$ vertices. Furthermore, if each vertex has a probability $p_k$ of having $k$ neighbors, ...
0
votes
2answers
70 views

How many trees are in the spanning forest of a graph?

Spanning forest is defined by the following definition: A forest that contains every vertex of G such that two vertices are in the same tree of the forest when there is a path in G between these two ...
-1
votes
2answers
50 views

Number of paths with length 3 in a wheel graph [closed]

How would I count the number of 3 length paths in a wheel graph where $n >= 2$?
0
votes
2answers
33 views

Finding paths in a graph with n vertices

Let n ≥ 2 be a natural number. Consider the graph G = (V, E) where V ={0,1,2,...,n} and E=({0,1},{0,2},...,{0,n}) ∪ ({1,2},...,{n−1,n}) ∪ ({n,1}) For paths, it's a sequence of (non-repeating) ...
-6
votes
1answer
45 views

Discrete Math on Graphs [closed]

Can someone explain to me that how would I show that Is it possible for a simple graph with 6 vertices to have 42 edges?
-3
votes
1answer
40 views

Discrete Math On proving Graph Degree Sequence

Can someone please explain that how would I show or Prove that there is no graph with degree sequence (1, 1, 2, 3, 4, 4, 5, 7). Thanks
2
votes
2answers
48 views

Does there exist a simple graph with the degree sequence

Does there exist a simple graph with 7 vertices and the degree sequence {0,2,2,2,3,5,6}? I know that the Handshaking Lemma says that the sum of the degrees is twice the number of edges. In this case ...
1
vote
1answer
42 views

$M_{R^n}$; how to derive $n$ for transitive closure?

When finding the transitive closure of a relation $R$, I convert $R$ into a boolean matrix $M_R$, and find the union between $M_R$ and its powers up to $n$. $$M_{R^*} = M_{R^1} \lor M_{R^2} \lor ...
0
votes
1answer
40 views

Graph theory : How to find edges ??

A simple graph in which each pair of distinct vertices is joined by an edge is called a complete graph. We denote by Kn the complete graph on n vertices. A simple bipartite graph with bipartition ...
0
votes
0answers
33 views

Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition ...
1
vote
3answers
48 views

Error for graph Theory proof

I am looking for an error in the proof but I am not certain about it. Pretty sure it has something to do with how there is not always a cycle of length 3. Theorem 1. For every (undirected) graph ...
0
votes
0answers
30 views

Illustrate this proof about transversals with an example. Is there a typo?

Let $F = \{S_1,\dots,S_m\}$ and $G = \{T_1,\dots,T_m\}$ be two collections of subsets of a finite set $E$. A transversal for $F$ is a list of elements $s_1,\dots,s_m$, one coming from each set in ...
1
vote
0answers
14 views

Algorithm for Simple Graph Given Degree Sequence [duplicate]

Are there an algorithm that provides a fastest way to construct simple graph given a degree sequence? Are there any other interesting problems around this area that I might be overlooking and should ...
1
vote
2answers
22 views

Modeling properties of a graph?

There is an undirected graph modeling highways in Texas, the vertices are cities and the edges are highways. How would you model the property. "Even if you shut down one highway, you can get from any ...
1
vote
0answers
124 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
1
vote
0answers
36 views

showing that all convex polehedron graphs are 3-connected

I'm trying to figure out how to show that two nonadjacent vertices in the graph of a convex polyhedron can be disconnected from one another by the removal of at least three vertices. I know what a ...
0
votes
1answer
25 views

Provide a Proof of Inequalities for the Given Problem

Let A be known as a graph. By definition an independent set S is a group of vertices (could be 0 vertices, or could be all vertices) of A where there are no two vertices from S that are adjacent in ...
0
votes
1answer
48 views

Planar and Euler's Formula Question

If a connected planar graph has four regions and six vertices, how many edges will the graph have? (I believe the answer is 8 but I'm not positive) 1) 9 2) 8 3) 6 4) 7 Graph A = ({a,b,c,d,e,f,g}, ...
0
votes
1answer
23 views

In-degree and out-degree of two distinct vertices in a directed graph

I need to prove or give a counterexample that for all $n\ge2$ there exists a directed graph of order $n$ such that every pair of distinct vertices have different out-degrees and same in-degrees.
0
votes
1answer
59 views

Bipartite Graphs and Trees Questions

Which of the claims below is not equivalent to the rest? 1) Every cycle in a graph "B" has an even length 2) Graph "B" is bipartite 3) Graph "B" has two components that are connected. 4) Graph "B" ...