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
26 views

Eulerian Circuits

I have been tasked with coming up for algorithms for the following graphs if they are Eulerian: Cyclic - this is easy - All cyclic graphs are Eulerian and can be traversed in order from 1 to $n$. ...
1
vote
1answer
42 views

Prove that a 3-regular graph $G$ has a cut-vertex if and only if $G$ has a bridge.

Prove that a 3-regular graph $G$ has a cut-vertex if and only if $G$ has a bridge. Here is what I got so far <= Assume that $G$ is a 3-regular graph and $G$ has a bridge. Let $u,v \in V(G)$ ...
0
votes
0answers
61 views

What number is “b” in the following theorem?

In the following scientific paper (http://www.ggiakkoupis.name/papers/icalp14_dynamic.pdf?attredirects=0) I have read Theorem 1. (Site of George Giakkoupis: http://www.ggiakkoupis.name/, his papers: ...
3
votes
2answers
57 views

Coloring Graph with some constarints

if Graph G be a Cycle with Length=4. how many ways we can color this graph with at most $\lambda$ different color, in such a way that non of two adjacent vertex has a same color?
0
votes
1answer
8 views

Hamiltonian cycle on a subset of 2D points, constrained by a total length (traveling salesman variation)

We are given a list of 2d coordinates, each coordinate representing a node in a graph, and a scalar D, which is a constraint on total length of the cycle. The task is to find a Hamiltonian cycle on a ...
1
vote
1answer
23 views

directed graph and no directed cycles

Show that it is possible for a directed graph with $n$ vertices and no directed cycles to have $n(n−1)/2$ edges . I am approaching by saying $2$ vertices are required for $1$ edge, so total number of ...
1
vote
1answer
215 views

Is there software I can use to draw this graph?

So, I have this particular graph to consider. It has the vertex set $\{1,...,17\}$ and edge set $\{(i,j)|i+j ~\mbox{is prime}\}$. Define a cost function $c:E(G)\mapsto \mathbb{R}$ by setting ...
1
vote
1answer
10 views

Proving every 3-Regular graph with no cut-edge has a 1-factor

I have the proof in my textbook, but I'm stuck on a line (or two). Here's some context: Let $S \subseteq V(G)$. Count the edges between $S$ and the odd components of $G-S$, $o(G-S)$. Since $G$ is ...
4
votes
0answers
59 views

Can bipartite graphs have the following properties?

Let G be a bipartite graph with at least $3$ vertices. Can it have the following properties simultaneously ? $1$) Every vertex is start vertex of some hamiltonian path. $2$) It contains no ...
0
votes
0answers
23 views

Hardest case in checking for hamiltonicity?

The problem of checking if a given graph has a hamilton-cycle, is NP-complete. However, in practice, the known algorithm work well. I wonder if sparse graphs (only a few edges) are more difficult ...
4
votes
0answers
24 views

Is this the smallest graph with the desired properties?

The above graph has the following properties : $1$) Every vertex is start vertex of some hamiltonian path. $2$) It contains no hamiltonian cycle. $3$) It has no cycle of length $3$. $4$) It is ...
0
votes
0answers
26 views

Understanding a formula in OEIS

I was looking at this question: Embedding Mazes - Spanning Trees of a Grid Graph and one of the comments mentioned "See OEIS sequence A007341", which is here: A007341 Number of spanning ...
0
votes
2answers
50 views

All self-complementary trees [closed]

I am looking for all self-complementary trees. Could someone accompany me in this great adventure?
1
vote
2answers
25 views

Isomorphism vs equality of graphs

I have just started studying graph theory and having trouble with understanding the difference b/w isomorphism and equality of two graphs.According what I have studied so far, I am able to conclude ...
1
vote
1answer
30 views

How many edges are needed if at least there is an edge among any 3 vertices?

In a simple graph, how many edges are needed if at least there is an edge among any 3 vertices?
2
votes
0answers
32 views

What happens to the number of maximal cliques (and their size) as you delete one edge at a time from a complete graph?

Say one has a complete graph with 1 giant clique. As we delete an edge from it at a time, the number of maximal cliques might increase or at least, the size of the maximal clique has to decrease by ...
1
vote
1answer
34 views

Find the degree of remaining verticies

A simple graph G has 7 vertices and 9 edges. The degrees of some of its vertices are 2, 2, 4, 2. Furthermore, G is known to have an Euler circuit. Find the degrees of the remaining vertices, and draw ...
0
votes
1answer
21 views

Prove that a graph $G$ is a forest if and only if every induced subgraph of $G$ contain a vertex of degree at most $1$

Prove that a graph $G$ is a forest if and only if every induced subgraph of $G$ contain a vertex of degree at most $1$ => Let $G$ be a forest. Then $g$ is the collection of a bunch of trees. For the ...
3
votes
2answers
24 views

A certain tree $T$ of order $n$ contains only vertices of degree $1$ and $3$. Show that $T$ contain $\frac{n-2}{2}$ vertices of degree $3$.

A certain tree $T$ of order $n$ contains only vertices of degree $1$ and $3$. Show that $T$ contain $\frac{n-2}{2}$ vertices of degree $3$. Here is what i got so far: Since $T$ is a tree of order ...
1
vote
0answers
22 views

Proof for corollary of non-separable graph

IF $U$ and $W$ are disjoint sets of vertices in a non-separable graph $G$ of order $4$ or more with $|U|=|W|=2$, then $G$ contain two disjoint paths connecting the vertices of $U$ and vertices of $W$ ...
1
vote
0answers
27 views

Cycles of maximum length in a non-separable graph G.

I must prove that in a non-separable graph G, (non-separable: the removal of any vertex of G will result in a disconnected graph) let k= the maximum length of a cycle in G, and let C and C' both be ...
-3
votes
1answer
25 views

Clarification of Definitions and Distinctions between Paths, Walks, and Trails [closed]

How are the concepts of paths, walks and trails, in the context of graph theory, understood and differentiated?
0
votes
1answer
19 views

The number of spanning trees in a simple graph with no cut edges

Let $t(G)$ be the number of spanning trees in a graph $G$. Leg $e(G)$ be the number of edges in a graph $G$. For $G$ a simple graph with no cut edges yields: $t(G) \geq e(G)$ I believe it is true, ...
0
votes
1answer
31 views

Calculating the average degree/valency of vertices

If I were to let T be a tree with n vertices, what would be the average degree/valency of the vertices in T? How would I go about calculating this?
0
votes
1answer
48 views

Nearest neighbor problem

Hey guys I just got a tricky homework question. I'm not looking for a straight up answer just a nudge in the right direction. Heres the question. Your friend has dropped you at some point on ...
0
votes
0answers
16 views

Do these algorithms to construct the graphs with a particular property have any importance?

I found a semi-general solution to the following open-ended question and obtained the explicit algorithms to construct the graphs with the following special property. But does my solution have any ...
1
vote
1answer
50 views

Lower bound on counting perfect matchings in bipartite graph

Let $G=(V_1 \cup V_2,E)$ be a finite bipartite graph. If every vertex in $V_1$ has degree at least $r\le|V_1|$ and $G$ has a perfect matching, we want to show there are at least $r!$ complete ...
0
votes
0answers
9 views

Notation for the graph with edge coloring

I'm thinking of how to represent a graph with a specific edge coloring. I tried to use the following notation, but is there any other way to represent it? Let $G=(V,E)$ be a graph, and for an ...
2
votes
1answer
50 views

Graph theory problem - the number of common acquaintances

This problem is from the book Graph Theory by Bin Xiong. Although I tried to understand the authors answer, their explanation is unclear for me. The problem is as follows. There are n people ...
0
votes
0answers
18 views

“Let $a$, $b$ and $c$ be positive integers with a≤b≤c. Prove that exists a graph G with k(G)=a, λ(G) = b and δ(G) = c.”

Anyone can help me with this question ? I have some guess how to do it, but I don't know how to prove it formally. "Let $a$, $b$ and $c$ be positive integers with $a\le b\le c$. Prove that ...
1
vote
2answers
31 views

Graph Theory Coloring

There are some earthlings and 15 martians in a space shuttle. Each earth- ling shook hands with exactly 6 martians, and each martian shook hands with exactly 8 earthlings. How many earthlings are ...
0
votes
1answer
28 views

Graph Theory (Edges and coloring)

Show that $e(G) ≥ \binom{χ(G)}{2}$ for every graph G. Here, $e(G)$ represents the number of edges in the graph.
-1
votes
1answer
73 views

Finding a minimum weight spanning tree? [duplicate]

Letting W be the weighted graph created by taking a complete graph K5 on five vertices 1, 2, 3, 4, 5 with the weight of each edge {x,y} given by ({x,y})=x+y, How would I find a minimum weight ...
2
votes
2answers
29 views

Graph Theory Greedy Algorithm

Find a bipartite graph and an ordering of its vertices so that the greedy algorithm uses at least 2014 colors. I am unsure whether I just need to draw a graph (not sure how I would do it with two ...
1
vote
0answers
11 views

Selecting one number from each set with minimum variance

I have a dataset that I need to find several sets of "similar" looking events across many days, which leads to the following problem. Suppose I have $N \sim 500$ sets, each containing $N_j \in [5, ...
0
votes
1answer
77 views

Algorithm producing a minimum spanning tree?

I need to prove that the following algorithm produces a minimum spanning tree(MST) upon termination. I think, looking at the lecture notes, that I need to reduce the operations to red and blue rules ...
0
votes
1answer
33 views

Dimension of the cycle/bond space in graph theory

I'm going through the book 'Graph theory', written by Bondy and Murty. I'm currently trying to grasp the idea of bonds, but I find this a rather difficult concept. So my first question is if someone ...
1
vote
0answers
21 views

Shortest route with a requirements set

Suppose you have a weighted connected graph, $G(V, E)$, with $n$ nodes such that every node has a edge to every other node (a large clique). You are also given a set of sets, $\{l_1, l_2, ... l_n\}$ ...
0
votes
1answer
60 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ on five vertices 1, 2, 3, 4, 5 with the weight of each edge $\{x,y\}$ given by $(\{x,y\}) = x + y$, how would I find ...
1
vote
0answers
43 views

Convex planar graphs

A planar graph is called convex, if it can be drawn in a way such that every face, including the outer face is convex. Wikipedia states that a planar graph is convex if and only if it is a ...
2
votes
1answer
18 views

Round table arrrangement for 13 people using graph theory

13 Members of a new club ,meet each day for lunch at a round table. They decide to sit such that every memher has different neighbours at each lunch.How many days can this arrangement last? ...
0
votes
2answers
25 views

Prove that there is an orientation of $G$ in which no directed path has length $2$ if and only if $g$ is bipartite.

Let $G$ be a graph of order $n\geq3$. Prove that there is an orientation of $G$ in which no directed path has length $2$ if and only if $G$ is bipartite. I don't know if I understand this correctly, ...
0
votes
1answer
26 views

number of vertices a special graph

Suppose a tree G has exactly one vertex of degree i for each 2<=i<=m and all other vertices have degree 1. How many vertices does G have?
1
vote
0answers
33 views

Example of Normal Spanning Tree

A rooted tree $T\subseteq G$ is normal in $G$, if end vertices of every $T$-path in $G$ are comparable in tree order of $T$. A tree $T$ with root r induces a partial order called the tree order which ...
3
votes
2answers
99 views

Question about the proof of Ramsey's Theorem

I was reading up on a proof of Ramsey's Theorem and I can't understand this part of the proof: Pick a vertex $v$ from the graph, and partition the remaining vertices into two sets $M$ and $N$, ...
1
vote
1answer
45 views

For every vertex of a Graph G, k(G-v) = k(G) or k(G-v) = k(g) -1?

can you help me with my homework ? "Prove or desprove : Let $G $ be a nontrivial Graph. For every vertex of a Graph $G$, $k(G-v) = k(G)$ or $k(G-v) = k(g) -1$ " I think the answer is : "Once we ...
3
votes
1answer
77 views

Is there a graph with these properties?

Is there a simple undirected graph with the following properties ? Each vertex has at least degree $4$ Each vertex is start vertex of some hamiltonian path The graph does not contain a hamilton ...
0
votes
0answers
17 views

Pina's algorithm

I have difficulty to understand the Pina's algorithm for enumerating all cycle bases of the undirected graphs. -Could you please explain to me using a detailed example ?
1
vote
1answer
47 views

Cycles and faces in planar graphs

Let G be a connected planar graph. Supopose, we know all cycles of G. Is this enough to determine the length of the face boundaries ? In particular, are the lengths of the face boundaries unique ...
0
votes
1answer
44 views

Prove that if $D$ is a digraph such that $od(v) \geq k \geq 1$ for every $v \in V(D)$ then $D$ contain a cycle of length at least $k+1$

Prove that if $D$ is a digraph such that $od(v) \geq k \geq 1$ for every $v \in V(D)$ then $D$ contain a cycle of length at least $k+1$ I tried to prove this by induction. So here is what I got so ...