Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

0
votes
1answer
43 views

Drawing Graph from adjacancy list.

I'm struggling with drawing a graph from following exercise: Set of vertices in undirected graph Gn is built from words of length n from alphabet {a,b,c,d}. Two words are adjacent when they have ...
2
votes
2answers
81 views

Must $G$ be connected?

Let $G$ be a graph of order $n$. If deg $u$ $+$ deg $v$ $+$ deg $w$ $\geq n-1$ for every three pairwise nonadjacent vertices $u,v$ and $w$ of $G$, must $G$ be connected? I know that if $H$ is a graph ...
0
votes
1answer
50 views

Adding a point to shortest path

If there exists a set of n points in a 2D coordinate system and an n-dimensional vector V ...
0
votes
1answer
81 views

Maximal matching without weights

I'm studying for a graph theory exam. And while looking at some exams of previous years which were handed out by the professor, I found the following question. As I understand it, a maximal ...
0
votes
2answers
62 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 ...
1
vote
1answer
128 views

Find out chromatic number of graph if $deg(G) \leq 3$.

I have a graph, not necessarily connected, that I know for a fact has vertices with degrees at most $3$. I need to find it's chromatic number in polynomial time. Well then it's just a matter of ...
1
vote
1answer
170 views

Degree of a Vertex Problem

A graph $G$ has the property that every edge of $G$ joins an odd vertex with an even vertex. Show that $G$ is bipartite and has even size.
1
vote
0answers
47 views

Determine the number of simple 7-vertex, 4-regular graph that are pairwise non isomorphic.

I'm taking an introductory graph theory course and I am having trouble going about answering this question. I've been told to look at the graph compliment but I don't quite understand how that ties ...
3
votes
2answers
38 views

Graph Theory Vertex Problem

Let $G$ be a graph of order $8$ with $V(G)=\{v_1, v_2,...,v_8\}$ such that deg $v_i=i$ for $1 \leq i \leq 7$. What is deg $v_8$. Any help or hints would be greatly appreciated.
1
vote
1answer
60 views

class 1 vs class 2 of graphs

Vizing's theorem states that a graph can be edge-colored in either $\Delta$ or $\Delta+1$ colors, where $\Delta$ is the maximum degree of the graph. A graph with edge chromatic number equal to ...
1
vote
1answer
111 views

chromatic number of a graph embedded on torus

if the graph G can be embedded on a torus can we say: if $\chi(G)\ge r\Rightarrow K_r\prec G$. Kr is a minor of G?
0
votes
1answer
188 views

Algorithm for creating adjacency matrix

Is it possible to create a graph ( represented in the form of Adjacency Matrix), when the number of nodes and the count of neighbors for each node is given?
0
votes
1answer
83 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!
11
votes
1answer
181 views

Isomorphism for Infinite Graphs.

Suppose that $G$ and $H$ are infinite graphs and that $G$ is isomorphic to a subgraph of $H$ and $H$ is isomorphic to a subgraph of $G$. Must $G$ and $H$ be isomorphic? I've only just started on ...
0
votes
2answers
51 views

Vertex Degree Proof

The degree of every vertex of a graph $G$ of order $2n+1\geq5$ is either $n+1$ or $n+2$. Prove that $G$ contains at least $n+1$ vertices of degree $n+2$ or at least $n+2$ vertices of degree $n+1$.
0
votes
3answers
77 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.
1
vote
2answers
60 views

Let $G$ be a graph. $G$ is graceful $\Rightarrow G$ is connected?

Let $G$ be a graph. Is the following implication true ? $G$ is graceful $\Rightarrow G$ is connected Definition: Let $G$ be a graph with $m$ edges. $G$ is graceful if there exists an injection ...
10
votes
1answer
601 views

Expected value of the distance square

Given two points $X,Y$ on two sides of square $[0,1]\times [0,1]$ ($X:(0,1/2),Y:(1,1/2)$ (PS: My original question is $X,Y$ on opposite of a square, but I think that's not the real case) )and $n$ ...
1
vote
1answer
85 views

edge coloring of a specific graph

For the graph $D_n$ created from complete graph $K_n$ by replacing one of edges by path on 3 vertices. For example, the graph attached is $D_4$. I can prove that the edge chromatic number is $n$. ...
3
votes
1answer
121 views

$K_{1,3}$ packing in a triangulated planar graph

I am trying to show that every planar triangulated graph $G=(V,E)$ with $|V| \ge 5$ has an edge decomposition into $|V| - 2$ groups of $K_{1,3}$. In other words, that we can pack $|V| - 2$ instances ...
2
votes
1answer
113 views

A question about the interlacing of symmetric matrices (graph interlacing)

Reading the paper of Haemers on graph interlacing I came across the following question. Let $A$ be a real symmetric matrix partitioned into $m \times m$ blocks and suppose $B$ is a $m \times m$ ...
0
votes
2answers
140 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 ...
5
votes
1answer
162 views

clique number of generalized Johnson graph $J(4n-1,2n-1,n-1)$

The generalized Johnson graph $J(v,k,r)$ is defined to be the graph whose vertex set is the set of all $k$-element subsets of $\{1,2,\ldots,v\}$, and with two vertices adjacent iff their intersection ...
2
votes
1answer
61 views

Number of triangles in a graph

Could anybody explain to my why the asymptotic upper bound for the number of triangles in a graph with n vertices is O(n^3). I could not imagine a graph with n vertices which can contain indeed n^3 ...
4
votes
3answers
175 views

Graph Theory: Simple Graph

Show that, if $G$ is simple, the edge graph of $G$ has $E(G)$ vertices and $\sum {d(v) \choose 2}$ edges. I know that an edge graph of a graph $G$ is the graph with vertex set $E(G)$ in which $2$ ...
1
vote
2answers
74 views

Strongly Connected Components

A strongly connected component in a digraph is defined as a subgraph where every vertex is reachable from every other vertex. I'm wondering if a seemingly related property exists for undirected graphs ...
0
votes
2answers
328 views

Graph Theory Question: Show that, in any group of 2 or more people, there are always 2 with exactly the same number of friends inside the group.

Show that, in any group of 2 or more people, there are always 2 with exactly the same number of friends inside the group. So, intuitively, this makes perfect sense, but I am having some trouble ...
1
vote
4answers
384 views

Bipartite proof

Let $G$ be a graph of order $5$ or more. Prove that at most one of $G$ and "$G$ complement" is bipartite. I'm lost as to what needs to be done. I know that A nontrivial graph $G$ is bipartite if and ...
1
vote
1answer
24 views

Let $r$ be the length of the shortest cycle in a graph $G$. When does $\dfrac{r}{r-2}=\dfrac{|E|}{|V|-2}$

Let $r$ be the length of the shortest cycle in a graph $G$. When does $\dfrac{r}{r-2}=\dfrac{|E|}{|V|-2}$ So far I've managed to establish, that the following equation is true for cyclic graphs ...
4
votes
2answers
87 views

Graph Theory. Prove that $\sum_{v}^{} \frac{1}{1+d(v)} \ge \frac{n^2}{2e+n} $

Let e denote the number of edges and n the number of vertices. We can assume that the graph G is simple. Prove that $\sum_{v}^{} \frac{1}{1+d(v)} \ge \frac{n^2}{2e+n} $ Any help/hints would be ...
2
votes
1answer
71 views

Maximum independent sets of balanced bipartite graph

Suppose that $G=(V,E)$ is a connected bipartite graph with $|V|=N$ and vertex set bipartition $V = A \cup B$ such that $|A|=|B|$. Assume that $\alpha(G) = N/2$. Is it always true that $A$ and $B$ are ...
2
votes
1answer
62 views

Number of trees of a certain size

Given a branching factor $b$ and a tree height $h$, a complete tree has $\sum_{i=0}^h b^i$ nodes. Define a partial tree as a sub-tree of the complete tree, with the same root. How many such partial ...
2
votes
4answers
612 views

The fundamental group of Cayley graph

Today I read a math book and find interested in Theorem. Every group has its graph representation. And we call it cayley graph. Now we sort out the question Firstly, if we have a group, ...
0
votes
1answer
69 views

Flow network: Source with in degree and sink with out degree

I have a flow network G with a single source s and a single sink t, but out-degree(t) is not 0 and in-degree(s) is not 0. Does removing all the edges leaving t and/or entering s change the capacity ...
0
votes
1answer
151 views

Probability of having a complete random graph

What is the probability that a random graph G(n,p) with n nodes and probability p = c some constant value is complete? By complete I mean that every pair of nodes ...
2
votes
1answer
223 views

Sequential algorithm for coloring graphs- there exists an ordering of vertices where it finds a coloring with $\chi(G)$ colors.

The sequential algorithm for coloring graphs is as follows Put vertices in the queue $ v_1,v_2,...,v_n$ in the order of your choice. Take out vertices from the queue and color them with the ...
1
vote
2answers
243 views

How to detect whether the two graphs are topologically equivalent

From this link I construct a regular graph .How to construct a k-regular graph? 10-4 regular graph: here is one m choose ...
2
votes
0answers
73 views

Is this graph problem already solved

I would like to solve the following: Let $G=(V,E)$ be a directed graph such as $\forall (x,y) \in E, x \neq y$. Find any (all would be even better) graphs $S$ such that: $S \subset V$ $\#\{(x,y) ...
2
votes
0answers
61 views

Graph Connectivity

I am given an initial connected graph $G$ with $n$ nodes and $m$ edges. At each step I remove an edge from $G$ and ask if $G$ is connected. Can the queries be answered in $\mathcal{O}(\log n)$ time ...
1
vote
1answer
60 views

Number of vertices of degree 1 - Expectation and Variance

Let $G\in G(n,p),0\le p\le \binom n 2=N$ where $G(n,p)$ consists of all $\binom N p$ subgraphs of $K_n$ with $p$ edges. Now let $X$ be the number of vertices of degree $1$ in $G\in G(n,p)$. Why is ...
2
votes
1answer
161 views

Is there a name for this property of a binary relation? $\forall x\forall y(x\mathsf{R}y\to\exists z(x\mathsf{R}z\land y\mathsf{R}z)))$

Consider a binary relation $\mathsf{R}$ such that $x\mathsf{R}y$ is the case only if there is some $z$ such that both $x\mathsf{R}z$ and $y\mathsf{R}z$ are the case. Is there a well-known name for the ...
17
votes
3answers
362 views

Results in graph theory proved using other areas of math, and vice versa

I'm curious about learning graph theory, as it seems to pop up in some unexpected places. In order to get a partial feel for the subject, I was wondering if anyone could point me to some survey ...
1
vote
0answers
107 views

zarankiewicz problem lower bound

I was just reading through the following article: http://page.mi.fu-berlin.de/szabo/PDF/stoc96.pdf On page 2 they give an explicit formula for the lower bound of the size of the graph. Summary: We ...
3
votes
1answer
151 views

Prove, that graph $G$ has at least $\chi(G)(\chi(G)-1)/2$ edges.

Can anybody give me any hints about how to prove that for any graph $G$ the number of edges in it is at least $\chi(G)(\chi(G)-1)/2$? $\chi(G)$ is the minimal number of colors we need to use to color ...
3
votes
1answer
36 views

Families of graphs where the shortest path between vertices uniquely determines vertex pairs

Imagine a graph $G$ with unlabeled vertices and unlabeled edges, and where we have an arbitrary vertex pair $(v_1,v_2)$. Let $k$ be the length of the shortest edge-wise path between $v_1$ and $v_2$. ...
3
votes
3answers
70 views

Comparison of almost planar graphs

I have multiple graphs all of which are almost planar. Is there any existing terminology / method which compares them, such that one can say which one is more planar? This could simply be the required ...
1
vote
1answer
111 views

Uncountable monochromatic set

Maybe you can help me with that. I was asking myself if you take an uncountable set $S$ and let $S^{(2)}$ be 2-coloured, must there exist an uncountable monochromatic set in $S$?
1
vote
1answer
63 views

Special Ramsey number $r(G)$

With $r(G)$ I refer to the smallest $n$ such that every blue-red colouring of the edges of $K_n$ contains a monochromatic copy of the grpah $G$ (this exists because $r(G)\le R(|G|)$). Now let $I_k$ ...
1
vote
1answer
102 views

If almost all random graphs $G \in g(n,p)$ have property $P_1$ and $P_2$ then almost all graphs have property $P_1 \cap P_2$

If almost all graphs $G \in g(n,p)$ have a graph property $P_1$ and almost all graphs $G \in g(n,p)$ have a graph property $P_2$ then almost all $G \in g(n,p)$ have the property $P_1 \cap P_2$. ...
2
votes
1answer
71 views

Prove that if $G$ is planar, then $G'e$ is planar too.

I need to prove that if graph $G$ is planar, then a graph created from it by joining two vertices $v,u$ on edge $e$ and connecting to a newly created vertex all others that were connected to either ...