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

1
vote
0answers
21 views

Hypergraph coloring

I hawe the following task: Decide if all 4-uniform hypergraph with fourteen hyperedges can be colored with 2 colors. I think that the answer is yes, but how can i prove it?
-2
votes
1answer
39 views

On path between two vertices of diffenent colour.

whether for a k-chromatic connected graph on n vertices,every pair of distinct coloured vertices are joined by atleast one path of odd length when the graph is coloured with exactly k number of ...
0
votes
1answer
56 views

Prove a graph is planar

I am kinda new to graph theory so I appreciate any suggestion or hint to approach this question. Thank you! Suppose a graph G does not have K2,2 as a subgraph. Suppose also that G has exactly 4 ...
4
votes
1answer
70 views

Graph Theory (maybe related to handshake lemma?)

In Alaska there are three caves with n bears in each of them. They are friendly bears, so every bear from any of the caves is on speaking terms with at least n+1 bears from the other two schools. Show ...
0
votes
1answer
31 views

Graph theory, order divisible by 3

Let G be a graph such that every vertex is in exactly ten triangles (10 distinct subgraphs with are isomorphic to K$_3$). Prove that the order of the graph is divisible by 3. I think this might ...
1
vote
1answer
11 views

Every vertex in a caterpillar graph is adjacent to at most two non-leaf vertices

I am not sure about my proof that goes: Use induction on the number of vertex of caterpillar graph, C. Base case, C with n=1 holds since it is a adjacent to no vertex. So the claim holds. Inductive ...
1
vote
1answer
19 views

Graph theory, trees, show T is subgraph of G

Let T be a tree with n vertices. G be a non-empty graph with $\delta$(G) $\ge$ n-1. Prove that T is a subgraph of G. If it's a tree then I know it has to be connected and if the minimum degree is ...
8
votes
4answers
635 views

Generalized graph theory

This question may be kind of 'out there' but it got me thinking. In graph theory we have a set of vertices $V$ and a set of edges $E$ which is made up of 2-element subsets of $V$ (either unordered or ...
2
votes
2answers
50 views

Graph Theory triangle (3 colors) [duplicate]

Show that if the edges of $K_n$ are colored with $n$ different colors, then there must be a triangle where all three edges have distinct colors. So, I want to use induction on $n$ where $n$ is the ...
3
votes
2answers
31 views

Boys, girls. Solve problem using edge-colouring.

In a class each boy knows precisely $d$ girls and each girl knows precisely $d $ boys. Use a result on edge-colouring to show that the boys and girls can be paired off in friendly pairs in at least ...
1
vote
1answer
31 views

Calculating connected components in an undirected graph

Suppose that we have a graph $G$ with $n$ vertices and $n-k$ edges, such that it does not include any cycles. How many connected components does it have?
0
votes
1answer
42 views

How many nonisomorphic graphs are there with 10 vertices and 43 edges?

How would I go about solving this? I know that $K_{10}$ has $9+8+7+\dots+1=45$ edges. So would it be something like $\binom {45}{43}$ because out of the 45 total edges, one must choose 43 for the ...
1
vote
0answers
46 views

Inequality in inverse Laplacian

I have the following problem, which is motivated by geometric diffusion on a directed graph. Conjecture. Let $A \in [0,1]^{n\times n}$ be strictly substochastic - i.e. $\forall i ~ \sum_j A_{i,j} ...
1
vote
1answer
35 views

Colouring graph's edges.

Let $G$ be a graph in which each vertex except one has degree $d$. Show that if $G$ can be edge-coloured in $d$ colours then (1) $G$ has an odd number of vertices, (2) $G$ has a vertex of degree ...
1
vote
2answers
29 views

What is “the crossing number inequality”?

Could someone explain to me what "The crossing number inequality" is? How is it different from the crossing number of a graph?
0
votes
1answer
22 views

Route inspection of special directed graph

You have a directed graph that is symmetrical in the sense that iff there is an A->B edge then B->A exists as well. Does this graph always have an Euler circuit without repeating any edges (assuming ...
3
votes
0answers
35 views

Number of Secret Santa directed graph with a largest cycle of given size

Secret Santa is a Western Christmas tradition in which members of a group are randomly assigned another member of a group for whom they are to buy a gift. While we were doing the random assignment ...
1
vote
1answer
13 views

Proper $n$-coloring of a graph clarification

There exists a theorem that states: Let G be a planar graph. There exists a proper 6-coloring of G. Any single-vertex graph $T$ is a planar graph. However, $T$ surely cannot be colored using all six ...
-2
votes
1answer
88 views

Graph Theory: Kruskal’s algorithm and Prim’s algorithm

A pipeline is to be built that will link six cities. The cos(in hundreds of millions of dollars) of constructing each potential link depends on distance and terrain and is shown in the weighted graph ...
1
vote
0answers
26 views

How to check homeomorphic embedding relation programmatically?

This is a follow up to this question and Deedlit's answer. I'm looking for a precise definition of the "hem?" (tree A homeomorphically embeddable in tree B?) relation, preferably in terms of a ...
3
votes
1answer
64 views

Cube color matching Graph Theory problem

I'm trying to solve a problem: Suppose you are given four cubes with each of the six faces painted with one of the colors red, white, green, or yellow. Use graph theory to place the cubes in a ...
0
votes
1answer
17 views

What is a Euclidean Graph? Can edges be negative in a Euclidean Graph?

To my understanding a graph is Euclidean if each edges connecting two vertices represents the distance between those two vertices, where the vertices are points in a plane. This is all I found in the ...
0
votes
1answer
76 views

How can I count the number of ways to connect a graph with $X$ vertices and $Y$ edges?

If I have a graph with $X$ vertices, and $Y$ edges, where $Y$ is between $X-1$ and $(X(X-1))/2$, how can I count the number of unique ways to connect the graph (strictly no more than two paths between ...
1
vote
1answer
35 views

Determining Information about a Graph Using the Degree Sequence

Let the following sequence be the degree sequence of the vertices of a graph with $n=10$ vertices. $\{6,6,4,4,4,4,2,2,2,2\}$ Is it possible to determine from this information whether this graph ...
1
vote
0answers
9 views

Potentials and Markov Processes

Given a resistive electrical circuit $G$, i.e. a graph with nonzero weights attached to each edge whose reciprocal we call the "resistance," we can define a reversible markov chain on the graph, ...
0
votes
0answers
24 views

Find mean value of amount of Hamiltonian cycles in the random complete directed graph

We are given the random tournament (randomized uniformly) on $n$ vertices. Task is to find the average value of the amount of Hamilton cycles on that tournament. This problem was covered in the ...
1
vote
1answer
27 views

Semi-hamiltonian graph.

A graph $G = (V, E)$ is semi-Hamiltonian if it possesses a path which uses each vertex of the graph exactly once. Given is $G = (V,E) $ Show, that if $\deg (u) + \deg (v) \ge |V| - 1 $ for each ...
0
votes
1answer
53 views

Modification of the Ramsey number

Let us denote by $n=r(k_1,k_2,\ldots,k_s)$ the minimal number of vertices such that for every coloring of the edges of the complete graph $K_n$ by $s$ different colors, there is some color $1\le i\le ...
1
vote
1answer
35 views

show that χ(G)≤√(2|E|)

I was given an Homework exercise where I need to show that χ(G)≤√(2|E|) So far I've manged to prove that: 1. χ(G)+χ(G′)≤n+1 2. χ(G)≤maximin{di,i} Now I tried using (1) because I know that there's ...
3
votes
2answers
115 views

Upper Bound on the Chromatic Number of a Graph with No Two Disjoint Odd Cycles

Prove that if a graph does not have two disjoint odd cycles then χ(G) ≤ 5, where χ(G) denotes the minimum number of colors needed to color the vertices of G. χ(G) is the chromatic number of G. ...
1
vote
3answers
41 views

number of edges induction proof

Proof by induction that the complete graph $K_{n}$ has $n(n-1)/2$ edges. I know how to do the induction step I'm just a little confused on what the left side of my equation should be. $E = n(n-1)/2$ ...
1
vote
1answer
65 views

Connected graphs, Euler circuits and paths, vertices of odd degree

I already have the solved the following questions. Just need to confirm my answers. Question 1: Prove that a connected graph G with at least two vertices is connected has an Euler circuit if and only ...
0
votes
0answers
29 views

Why is it not possible to draw the $\overline{Q_3}$ in the plane

I am trying to prove that $\overline{Q_3}$ is nonplanar. I know that $Q_3$ is planar and I have attempted to use the corollaries derived from Euler's planarity Theorem to show it is nonplanar but it ...
0
votes
2answers
37 views

Graph theory possibilities

Is it possible to have a simple graph(no loops or parallel edges), connected, six vertices, six edges? Is it possible to have a graph, connected, ten vertices, nine edges, nontrivial circuit? Is it ...
1
vote
2answers
49 views

Perfect matching in bipartite graphs

Prove that a bipartite graph has a perfect matching $\iff$ $\vert N(S)\vert\geq \vert S \vert $ for all $S \subseteq V$. (For any set S of vertices in G we define the neighbor set N(S) of S in G to be ...
3
votes
1answer
25 views

Prove chromatic polynomial of n-cycle

Let graph $C_n$ denote a cycle with $n$ edges and $n$ vertices where $n$ is a nonnegative integer. Let $P(G, x)$ denote the number of proper colorings of some graph $G$ using $x$ colors. Theorem: ...
1
vote
1answer
40 views

In graph theory, what does $o(G)$ usually mean?

I'm completing a graph theory assignment, and one of the problems states, Prove that a tree $T$ has a perfect matching if and only if $o(T-v) = 1$ for every $v \in V (T)$. I'm not asking for ...
0
votes
2answers
16 views

DFS step-wise go through the adjacency list

DFS on a graph G = (V, E) in adjacency list representation: ...
1
vote
2answers
28 views

Every power of adjacency matrix contains zeroes

I need to find connected graph $G = (V, E), |V| \geq 3$ such that every power of his adjacency matrix contains zeroes. I know that that graph will be path and adjacency matrix for even and odd powers ...
2
votes
1answer
48 views

Lovasz Extension of the Product of Functions

Let $f$ and $g$ be submodular functions, and let $\widehat{f}$ and $\widehat{g}$ be the Lovasz extensions of $f$ and $g$, respectively. What can we say about the Lovasz extension of $f \times g$, ...
0
votes
1answer
42 views

Hamiltonian graphs and card shuffles

I am solving the example on Hamiltonian graphs: We have 3 players of unique a game, there are 57 special cards. We know that by the rules of the game we can play only react to one card by 30 ...
0
votes
1answer
43 views

Cocktail Party/Graph Theory Problem

15 people are at a party. If in every group of 3 people, at least 2 do not know each other, what is the greatest possible number of pairs of people that know each other? I've been working on this for ...
0
votes
2answers
41 views

Question on Graphs?

I'm reading a book on Discrete Math and came upon this Definition in the Chapter of Graphs which I can't understand. Can anyone help me understand its meaning? Definition: The set of all neighbours ...
-1
votes
0answers
30 views

how many 3 regular graphs are there? [duplicate]

I have an exercise for my math study, and I think I know the answer, but I'm not sure. How many 3 regular graphs are there with vertices {1,2,3,4,5,6}? I know there are a few sites on the internet ...
1
vote
0answers
54 views

Prove $\lambda=\min_{i = 1,\ldots, n}\max_{0 \le k \le n-1}\left(\frac {p_i(n)-p_i(k)}{n-k}\right)$

Prove the minimum directed cycle mean cost satisfies: $\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)$ using the Bellman-Ford algorithm. Let ...
1
vote
1answer
43 views

What is the meaning of V\U?

What is the meaning of U \ V when it comes to graph? I try to understand Markov property on DGM with below document but for me it is hard to search. ...
1
vote
1answer
33 views

Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost.

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
3
votes
1answer
156 views

Proof that connected graph contains connected graphs

Let $G = (V, E)$ be connected graph with at least three vertices. How would one proof that $G$ contains vertices $u, v \in V$ such that all three graphs: $G$ without $v$, G without $u$, G without $u$ ...
0
votes
1answer
50 views

how many 2 and 3 regular graphs are there?

I have two questions for my mathematic study. I think I know the answer of the first, but I'm not sure. A) How many 2 regular graphs are there with verticles 1,2,3,4,5? I think the answer is 4!/2 = ...
0
votes
0answers
16 views

Graph Bipartition - Normalized cuts

Can anyone explain me how to do the cut in a graph in the Normalized cuts algorithm descriped here: http://web.cs.ucdavis.edu/~bai/ECS231/returnsfinal/WangH.pdf (page 3 bottom)? I have an image, a ...