# Tagged Questions

211 views

### Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
32 views

### T and F on some discrete math concepts

I was studying and these questions came up on a review guide on the inter webs, but could was wondering if I was correct on them. 1.Let $B$ $\subset$ $A$ and $f$ : $B$ $\subset$ $A$ be a 1-1 and ...
38 views

### Show that if G is a simple graph with at least 4 vertices and 2n-3 edges, it must have two cycles of the same length.

For $n\ge4$, let G be a simple n-vertex graph with at least $2n - 3$ edges. Prove >that G has two cycles of equal length. (West's Introduction to Graph Theory Q 2.1.42) I am trying to prove the ...
56 views

### Graph Coloring Question

Given T(n) as a star graph with n edges. (Basically T(n) is a graph that has one vertex u in the center, and from u there is one edge to each vertex v1,...,vn.) It is easily know that star-graphs are ...
28 views

### Partition complete graphs

If I have $K_n$, and I want to partition edges of $K_n$ into edges sets of complete graphs $G_1,...G_k$, then I need to show $n \le k$. My approach was thinking of $K_5$ which is a partition of $5$ ...
22 views

### Adjacency matrix of strongly connected digraph

If I have $A$ the adjacency of a strongly connected digraph, I want to show: For $\lambda$ satisfying $Ae= \lambda e$ for nonegative $e$, I want to show for any eigenvector (could be negative), the ...
45 views

### How to find the planar embedding of a graph in general?

I need to find the planar embedding of a graph in general if one exists and specifically want to solve the problem for the graph in the figure below. I am acquainted with the graph algorithms but have ...
63 views

### Graph Theory - Introduction Questions [closed]

I have a couple of questions that are probably SUPER easy for anybody that has studied graph theory but are confusing the hell out of me. I know it may be inconvenient to help me but I have a test ...
35 views

### How to prove $G$ is Eulerian

We know that a Eulerian graph has vertices all are even. But how can we prove the sufficiency of it i.e. if a connected graph $G$ has vertices all are even, then how can we prove the graph $G$ is ...
31 views

### Number of triangles in a Graph/Network

Given An undirected graph/Network, and its adjacency matrix A, and 1 (A column vector with all elements as 1). How do we represent the problem of finding the number of triangles in the network ...
46 views

### Chromatic polynomial for a bipartite graph

I need to get the chromatic polynomial for the complete bipartite graph: $K_{2,3}$ Im using the Fundamental Reduction Theorem, and the picture below shows mi attempt to it. I omitted vertex names ...
180 views

### Maximum size of a bipartite subgraph on a random graph

Show that almost every $G \in \mathscr{G}(n,\frac{1}{2})$ contains no bipartite subgraph with more than $\frac{n^2}{8} + n^{\frac{3}{2}}$ edges. Tried using Markov's inequality by setting a = ...
23 views

### Prove the following statements about a graph G [closed]

G is connected diam(G) $\leq$ 10 G is bipartite G is vertex transitive So I don't need to prove these statements (since not enough information is given about the graph G) But if I did have enough ...
17 views

### The clique number ($\omega$) of a graph G is the largest integer k such that K_k is a subgraph of G

Prove that if G $\cong$ H then $\omega(G)=\omega(H)$. So this makes sense. But how do I go about proving it? I understand if two graphs are isomorphic then they are essentially the same and that ...
24 views

### Let G be a connected graph not having P_4 or C_3 as an induced subgraph. Prove that G is a complete bipartite graph

I understand what a complete bipartite graph is but am not sure how to relate that to a P_4 graph
54 views

### Prove that if G is connected then v $\in$ V(G) has a neighbor in every component of G-v

I understand what the question is asking but am not sure how to begin the proof. G-v is the set of vertices and edges which are in G but not v
44 views

### Graphs: Prove that $\operatorname{diam}(G \cdot H) \leq \operatorname{diam}(G)+\operatorname{diam}(H)$.

Let $G$ and $H$ be graphs. Prove that $\operatorname{diam}(G \cdot H) \leq \operatorname{diam}(G)+\operatorname{diam}(H)$. So I understand cross product of graphs but I am not sure where to start on ...
26 views

### Discrete Math Project

Any suggestions for a good project based on Graph theory or any basic topic in DMS for a college level project.I was planning to simulate a Page Rank algorithm on a small scale but I am still confused ...
48 views

### Prove that graph has at least one cycle of length at least $\delta+1$

I have to answer the question : "Is it true that in all finite graphs (connected graphs) wchich $\delta \ge 2$ ($\delta$ is the smallest degree of vertices in a graph) exists the cycle of length equal ...
37 views

### Coloring of $K_{17}$

For any 3-coloring of $K_{17}$ I have to show there exists either a red, blue or green triangle. To start, can I use proof by contradiction with color red, blue, green? So $(0,0,136)$ means all 136 ...
57 views

### Two coloring questions and ramsays number

What is the smallest $n$ such that every 2-coloring of edges of $K_n$ contains a red or blue 4-cycle (not $K_4$)? I am given that $R(4,4) \le 18$ and $R(3,5) \le 14$ Any help is greatly appreciated!
40 views

### Problem with proving that graph consisting of $n$ edges and $n$ vertices has only one circuit.

Is this true that graph consisting of $n$ edges and $n$ vertices has only one circuit. I drew some graphs on paper and I believe that it is true. But how to prove that? I will be glad for any help.
63 views

### Graphs exercises

a)Let graph $T=(V,E,f)$ where $|V|=n>1$ Prove that those statements are equivalents: T is a tree; For each $v$ $\in$ V there's only a path from $u$ to $v$. b) Let G a connected graph whose ...
12 views

### A consequence of edge-criticality

Let $G$ be $\Delta$-edge-critical (that is, $G$ is $\Delta + 1$-edge-chromatic and removing any edge of $G$ gives a subgraph which is at most $\Delta$-edge-chromatic, where $\Delta$ is the max degree ...
54 views

### pigeonhole principle related problem

I'm given the problem: In a tournament which 18 teams participate, a team being matched with another in a round don’t match again in the follwoing (later) rounds. After 8 rounds prove that there are 3 ...
33 views

### How does this theorem of Robertson, Seymour, and Thomas imply Hadwiger's conjecture for $k$ = 6?

The result in question is Theorem Every 6-contraction-critical graph $G \neq K_6$ has a vertex $x$ such that $G-x$ is planar. The article I'm reading ("A Survey of Hadwiger's Conjecture" by Bjarne ...
32 views

### On Hadwiger's conjecture for k=4.

I'm reading the article "A Survey of Hadwiger's Conjecture" by Bjarne Toft. Toft states that the following result implies Hadwiger's conjecture for the case $k=4$: Theorem. Let $G$ be edge-maximal ...
43 views

54 views

### Lower bound on the size of a maximal matching in a simple cycle

Let $C_n$ denote an undirected simple cycle of $n$ nodes. I want to determine a lower bound on the size of a maximal matching $M$ of $C_n$. Please note: A subset $M$ of the edges in $C_n$ is called a ...
53 views

### Trying to understanding the proof of the fact that Kazhdan property (T) implies expanders.

I am trying to trying to understanding the proof of the fact that Kazhdan property (T) implies expanders. This is a result of Grigory Margulis. It is stated in Proposition 3.3.1 on Page 30 of the book ...
35 views

### A bipartite graph with the degree sequence {5,5,5,5,5,8,8,8,8,8,8,8,8,9}

Does there exist a simple bipartite graph with the degree sequence {5,5,5,5,5,8,8,8,8,8,8,8,8,9}? I believe the answer is no but cannot prove this. Any assistance will be appreciated. Thanks
53 views

### N- dimensional hypercube graph problem

So I have this problem: Prove that the n-dimensional hypercube is a bipartite graph for every n bigger or equal to 2. All help is welcomed.
39 views

### Question on connected graphs

Is it true that if for each partition of a graph G's vertices into two non empty sets there is an edge with end points in both sides then G is connected? Intuitively this seems true to me. But I ...
38 views

### Showing that two given graphs are homeomorphic

I won't to verify whether the two graphs given above are homeomorphic. I am not sure of the method to verify this. I would much appreciate if anyone could give some assistance. Thanks
28 views

### Is an isolated vertex a component of a graph?

I want to know if an isolated vertex can be considered as a component of a graph. Answers will be appreciated.thanks
28 views

### Finding the diameter of a graph with a complex structure

I know the diameter of the above graph is 6. But I don't know a formal way of doing this. However I know it is possible to draw a matrix considering the minimum distance between the vertices but ...
36 views

### Mantel's Theorem proof verification

I found the following proof for Mantel's proof. I cannot understand the equality that I have highlighted in the image was arrived at. I would appreciate some assistance thanks
21 views

### Prove Eulerian directed path on a digraph

In an undirected and connected graph $G$, replace each edge by a pair of directed edges (round trip). How can I prove that the resulting digraph has an Eulerian directed path?
66 views

### Graph theory people at a round table problem

So I have this problem: There are 20 people at a party and each one of them is friends with at least 10 of the people. They all sit at a round table. Prove that there is a way to place the people on ...
58 views

### Finding the diameter of a n-cube

Is there a general method that can be used find the diameter of a n-cube? In particular what if I want to find the diameter of a 4-cube can someone suggest me a method or hint. I would much appreciate ...
57 views

### Clarifying Dirac's theorem

Theorem : If $G$ is a simple graph with $n$ vertices with $n ≥ 3$ such that the degree of every vertex in G is at least $n/2$, then $G$ has a Hamilton circuit. In this if $n$ is odd, should I ...
21 views

### Necessary and sufficient condition for an Euler circuit

I have come across the theorem A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree. I just want to know whether the same holds ...
21 views

### Expansion of subsets of a hamming ball in hypercube

Consider a hypercube graph $G_n = (V,E)$ in n dimensions. Let $H_{1/2} \subset V$ be the set which represents the hamming ball of radius $n/2$. That is for every $v \in H_{1/2}$ the hamming weight of ...
68 views

### 3-dimensional cube shortest path question

Let Q be the graph consisting of vertices and edges of a 3-dimensional cube. Two relations are defined on the vertices of Q. • R1={(v,w):the shortest path from v to w has an odd number of edges}. ...
58 views

### A $C_3$ free graph, degrees inequality

If $G$ is a $C_3$ free graph, for any edge $(x,y)$ of $G$ I need to prove that $$\deg(x)+\deg(y)<|V(G)|+1.$$Any hints/answers will be much appreciated. Thanks
106 views

### to find the graphs having vertices with same eccentricity

I was reading a paper http://www.discuss.wmie.uz.zgora.pl/php/discuss3.php?ip=&url=plik&nIdA=11134&sTyp=HTML&nIdSesji=-1 There is a formula to calculate eccentricity in the section ...
40 views

### maximum number of pendant vertices in a graph

Can anybody help me in providing a simple hint to my problem. I was just thinking how many pendant vertices a graph can have where diameter of the graph, $diam(G)\geq3$, after leaving the graph $P_4$. ...