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

Longest Path in a acyclic, directed graph

Is there a known algorithm which finds the longest path in an acyclic, directed graph like the one below? For this example, the algorithm should calculcate a longest path of 28m
0
votes
1answer
59 views

Relation between independence number and channel capacity

Suppose $P_{Y|X}$ is a discrete memoryless channel with confusability graph $G$ and capacity $C = max_{P_X}I(X; Y )$. I want to prove the following relation: $\log{\alpha(G)}\le C$ where $\alpha(G)$ ...
0
votes
3answers
401 views

Perfect matching in k-cubes

I want to show that every k-cube has a perfect matching for $ k \geqslant 1 $. (A k-cube is a graph whose vertices are labeled by k-tuples consisting of $ 0 $ and $1$ , and each two adjacent vertices ...
0
votes
2answers
122 views

In how many ways you can represent a graph ( data type )?

I need some references that go beyond the classical and graphical representation of a graph with vertices and edges; I'm trying to dive into the math world and see if I can get an alternative ...
1
vote
1answer
72 views

Simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph

Why a simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph? In my notes, it says it is easy and leave as an exercise with a hint which want us to show the ...
0
votes
1answer
44 views

Expectation of number of links to N selected nodes in a network

Take a directed graph denoted by its adjacency matrix $\mathbf{A}$. It is a probabilistic graph -- the nodes of $\mathbf{A}$ might be linked, and the entries are probabilities between 0 and 1. Say ...
0
votes
2answers
368 views

Proof NP-Complete for $L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$

$L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$ and I try to prove it's NP-Completeness. It seems really easy since obviously it is at least as hard as HAM-PATH which is ...
2
votes
1answer
43 views

Why doesn't Tutte polynomial T(1,1) equal 0?

If the formula for a Tutte polynomial is: then how does T(1,1) solve for spanning trees instead of just returning a 0?
4
votes
0answers
72 views

Question about Szemeredi's regularity lemma and eigenvalues of a graph

In the context of Szemeredi's regularity lemma, is there any way to relate the eigenvalues of the ambient graph with the densities of an $\epsilon$-regular partition? More precisely, if $V(G) = ...
1
vote
0answers
33 views

What is $F_P$ and $E(P)$?

I'm reading Handbook of Graph Theory: At this section, he speaks about $F_P$ and $E(P)$. It's not really clear what they are. I guess there is enough context for someone to answer me but if ...
1
vote
1answer
38 views

show that $\phi(B_n)$=smallest integer greater than or equal to $5n/2$

Let $A_i$ be a complete graph $K_n$ for all $1\le k\le 5$ and let $B_n$ be a graph which obtain from vertex disjoint union of $A_1,A_2,...,A_5$ by adding all possible edges between $A_i$ and ...
0
votes
0answers
24 views

Semi-complete partites

Is there a name for regular bipartite graphs where each partite has the semi-completeness property (that is, for each two vertices $i$,$v$ in the partite $V$, there is a path $\{i,w,v\}$, where $w$ ...
0
votes
1answer
57 views

How many graphs on the vertex set {1, …, 12} have exactly 15 edges?

I know that to solve this I have to figure out how many total possible edges there are However, I am unsure how to do this ? Once I am able to figure out the number of edges, I can choose 15 out of ...
0
votes
2answers
73 views

Graph without cycle length of 3.

Let $ G = (V, E) $ be a graph such that $ | V | = 2n $ for $ n \in \mathbb {N} $. Prove: $$ G \mbox{ has no cycle of length 3} \Rrightarrow | E | \le n ^ 2 $$ Please for advice. I'm trying solve it ...
1
vote
1answer
57 views

Amount of 3-cycle in complete graph.

Consider the complete graph $ K_n $ . How much is disjoint cycles of length three? Thanks in advance.
1
vote
1answer
62 views

Prove that a “prime graph” is Bipartite.

Let the prime graph be defined as the graph of all natural numbers, with two vertices being connected if the sum of the numbers on the two vertices add up to a prime number. Prove that the prime graph ...
1
vote
1answer
58 views

Chromatic index. Proof.

Let $\chi(G) $ denote the chromatic number of $G$. I need to prove that $$\chi(G)\left(\chi(G) -1\right) \le 2|E|. $$ And now I'm asking for help.
1
vote
0answers
35 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
53 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
78 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
105 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 caves. ...
0
votes
1answer
39 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
67 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
86 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 ...
10
votes
4answers
826 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
1answer
191 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
63 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
128 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
197 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 ...
2
votes
0answers
75 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
45 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
63 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
48 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
89 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
22 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
286 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
1answer
173 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 ...
4
votes
1answer
706 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
540 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
269 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
78 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
23 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, ...
1
vote
1answer
442 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
94 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
71 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
587 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. ...
2
votes
3answers
934 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
707 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
35 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
200 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 ...