text:
Codegolf Rainbow : Draw in Black-and-White
Introduction:
 (Source: Wikipedia)
When we look at a rainbow it will always have the colors from top to bottom:
Red; orange; yellow; green; blue; indigo; violet
If we look at these individual rings, the red ring is of course bigger than the violet ring.
In addition, it's also possible to have two or even three rainbow at the same time.
All this above combined will be used in this challenge:
Challenge:
Given an integer n, output that many rings of the (possibly more than one) 'rainbows', where we'll use the letters vibgyor for the colors.
See the test cases below to see how they are built upwards from n=1, and how the spacing should be handled (at n=8). As you can see, one space is added between two rainbows, including spacing at the top, before we add the ring of the next rainbow in line.
Challenge rules:

You are allowed to use capital VIBGYOR instead of lowercase
There should be a space between the individual rainbows
Any amount of leading and/or trailing spaces/new-lines are allowed, as long as the actual rainbow (wherever it is placed on the screen) is correct
The input will always be a positive integer (>= 1). The behavior when n=0 is therefore undefined, and the program/function can do whatever it wants (outputting nothing; outputting the rainbow of n=1; random output; fail with an error; etc.)
You are allowed to output a list/array of strings or 2D array/list of characters if you want (you could add the actual pretty-printing code in the TIO footer).
Ignore the fact that the outputs looks more like Mayan temples than rainbows.. xD

General rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, adding an explanation for your answer is highly recommended.

Test cases (first n=1 through n=10, and n=25):
1:
 vvv
v   v

2:
  iii
 ivvvi
iv   vi

3:
   bbb
  biiib
 bivvvib
biv   vib

4:
    ggg
   gbbbg
  gbiiibg
 gbivvvibg
gbiv   vibg

5:
     yyy
    ygggy
   ygbbbgy
  ygbiiibgy
 ygbivvvibgy
ygbiv   vibgy

6:
      ooo
     oyyyo
    oygggyo
   oygbbbgyo
  oygbiiibgyo
 oygbivvvibgyo
oygbiv   vibgyo

7:
       rrr
      rooor
     royyyor
    roygggyor
   roygbbbgyor
  roygbiiibgyor
 roygbivvvibgyor
roygbiv   vibgyor

8:
         vvv
        v   v
       v rrr v
      v rooor v
     v royyyor v
    v roygggyor v
   v roygbbbgyor v
  v roygbiiibgyor v
 v roygbivvvibgyor v
v roygbiv   vibgyor v

9:
          iii
         ivvvi
        iv   vi
       iv rrr vi
      iv rooor vi
     iv royyyor vi
    iv roygggyor vi
   iv roygbbbgyor vi
  iv roygbiiibgyor vi
 iv roygbivvvibgyor vi
iv roygbiv   vibgyor vi

10:
           bbb
          biiib
         bivvvib
        biv   vib
       biv rrr vib
      biv rooor vib
     biv royyyor vib
    biv roygggyor vib
   biv roygbbbgyor vib
  biv roygbiiibgyor vib
 biv roygbivvvibgyor vib
biv roygbiv   vibgyor vib

25:
                            ggg
                           gbbbg
                          gbiiibg
                         gbivvvibg
                        gbiv   vibg
                       gbiv rrr vibg
                      gbiv rooor vibg
                     gbiv royyyor vibg
                    gbiv roygggyor vibg
                   gbiv roygbbbgyor vibg
                  gbiv roygbiiibgyor vibg
                 gbiv roygbivvvibgyor vibg
                gbiv roygbiv   vibgyor vibg
               gbiv roygbiv rrr vibgyor vibg
              gbiv roygbiv rooor vibgyor vibg
             gbiv roygbiv royyyor vibgyor vibg
            gbiv roygbiv roygggyor vibgyor vibg
           gbiv roygbiv roygbbbgyor vibgyor vibg
          gbiv roygbiv roygbiiibgyor vibgyor vibg
         gbiv roygbiv roygbivvvibgyor vibgyor vibg
        gbiv roygbiv roygbiv   vibgyor vibgyor vibg
       gbiv roygbiv roygbiv rrr vibgyor vibgyor vibg
      gbiv roygbiv roygbiv rooor vibgyor vibgyor vibg
     gbiv roygbiv roygbiv royyyor vibgyor vibgyor vibg
    gbiv roygbiv roygbiv roygggyor vibgyor vibgyor vibg
   gbiv roygbiv roygbiv roygbbbgyor vibgyor vibgyor vibg
  gbiv roygbiv roygbiv roygbiiibgyor vibgyor vibgyor vibg
 gbiv roygbiv roygbiv roygbivvvibgyor vibgyor vibgyor vibg
gbiv roygbiv roygbiv roygbiv   vibgyor vibgyor vibgyor vibg

Maybe you know this and it's by design (I know that rainbows are not rhombuses or ascii, too, and higher orders' positions get more complicated), but aren't the colours reversed in the 2nd rainbow?

@ChrisM Ah, you're indeed right. With two rainbows the second is indeed reversed, but with three only the outer is reversed, and with four both outer are reversed. Ah well, bit too late to change it now. Maybe I'll think of a third related challenges with this later on. :)

@ChrisM Added a third related challenge implementing your comment to the Sandbox.

Oh cool, nice one :¬)

Python 2, 84 82 81 bytes
-2 bytes thanks to ElPedro.
n=input();n+=n/7;w=''
while-~n:w+=" vibgyor"[n%8];print' '*n+w+w[-1]+w[::-1];n-=1

Try it online!

Dyalog APL, 41 39 38 bytes
↑{⌽(⌽,⊃,A↑⊢)⍵↑A⍴' vibgyor'}¨-⍳A←⌈⎕×8÷7

Try it online!
A similar approach to others: A←⌈⎕×8÷7 finds the height of the rainbow (also the width of the longest 'half row' to the left/right of the centre) and assigns it to A for later use, while ¨-⍳ iterates through the values 1..A, negating them to select on the correct side when used with ↑.
A⍴' vibgyor' generates a 'half row' and ⍵↑ selects the correct length substring. (⌽,⊃,A↑⊢) generates the full row in reverse (which takes fewer characters to do), starting with a reversed half row (⌽), then the centre character taken from the beginning of the half row string (⊃) and finally a right padded version of the half row (A↑⊢). The final ⌽ reverses the row into the correct orientation and ↑ turns the vector of rows into a 2D array.
Edit: -2 thanks to dzaima
Edit: -1 thanks to ngn

You can replace ⍕⍪ with ↑ - outputting a 2D array of characters is allowed

39 bytes

1+÷7 -> 8÷7

Canvas, 29 28 26 bytes
７÷Ｕ＋｛ <ibgyor＠¹×／ｎ｝⇵Ｋ２＊∔─↶

Try it here!
Explanation:
7÷U+                          ceil(input/7) + input
    {             }         for n in 1..the above
      <ibgyor@                in the string " <ibgyor", pick the nth character
              ¹×              repeat n times
                /             create a diagonal of that
                 n            and overlap the top 2 stack items (the 1st time around this does nothing, leaving an item for the next iterations)
                   ⇵        reverse the result vertically
                    K       take off the last line (e.g. " <ibgyor <ib")
                     2*     repeat that vertically twice
                       ∔    and append that back to the diagonals
                        ─   palindromize vertically
                         ↶  and rotate 90° anti-clockwise. This rotates "<" to "v"

25 24 22 bytes after fixing that ｍold should cycle if the wanted length is bigger than the inputs length and fixing ／ for like the 10th time

Out of curiosity, why is the v sideways (<)? Is v already a reserved keyword in Canvas, if so, why not use < as that reversed keyword instead?

the characters are used vertically and then rotated, and Canvas is smart enough to figure out that < rotated 90° anticlockwise equals v :P All ASCII are part of strings in Canvas btw

Ah ok, so if you would have used v here, and you then rotate it 90 degrees counterclockwise, it becomes > instead. I see. :D

@KevinCruijssen That'd have other consequences too

Ah, you also have a mirror there somewhere? I can't read Canvas tbh, so I'm looking forward to the explanation of the code. ;)

JavaScript (ES6), 100 bytes
Returns an array of strings.
f=(n,a=[i='   '])=>++i<n+n/7?f(n,[c=' vibgyor'[i&7],...a].map(s=>c+s+c)):a.map(s=>' '.repeat(--i)+s)

Try it online!

05AB1E, 32 31 23 bytes
.•VvÈ©•¹∍¬„ v:RηεÂ¬ý}.c

Try it online!
-1 thanks to Kevin Cruijssen and -8 thanks to Adnan

Explanation (Stack example w/ input of 3):
.•VvÈ©•                  # Push 'aibgyor'           | ['aibgyor']
       ¹∍                # Extend to input length.  | ['aib']
         ¬               # Push head.               | ['aib','a']
          „ v:           # Replace with ' v'.       | [' vib']
              R          # Reverse.                 | ['biv ']
               η         # Prefixes.                | ['b', 'bi', 'biv', 'biv ']
                ε   }    # For each....             | []
                 Â¬ý     # Bifurcate, join by head. | ['b','b']       ->    ['bbb']
                                                    | ['bi','ib']     ->   ['biiib']
                                                    | ['biv','vib']   ->  ['bivvvib']
                                                    | ['biv ',' vib'] -> ['biv   vib']
                     .c # Center the result.        | Expected output.

"vibgyor" can be golfed by 1 byte to .•2Bãθ(•. (Here the explanation for it at the "How to compress strings not part of the dictionary?" section.) In addition, „vr…v r:ð« can be golfed to 'v„v .:. So 28 bytes. Nice answer though, +1 from me.

@KevinCruijssen oh I know all about string compression-- I just figured (as is usually the case with super small strings) that  the 3-byte bloat of .•• wouldn't save a byte. Figures the one time I don't actually check is the time it would save bytes xD. Good catch

Ah yes, you made the tip about the ASCII art compression with transliteral. Nice tip with code-generation btw, I used it recently in an answer of mine. I was also doubting it would work considering the three bytes of .••, but I figured I'd try anyway since  "" is also already 2 bytes, and it indeed saved a byte. :) EDIT: Your tip doesn't use String compression though, only number compression. Ah well. xD

@KevinCruijssen string compression came out ~5 months after I wrote that tip :P.

Ah lol. I have no idea what came out when. Sometimes I see very old answers from mid 2016 however which didn't even had implicit input yet, then I know it's an old version. ;p PS: In my first comment I mentioned something else to golf 3 more bytes.

@KevinCruijssen Didn't see that the first time. Bad habit of skimming comments/summaries. Unfortunately, that doesn't work for multiples of 7; you have to make sure we need the space due to the v AND the r existing. String compression was spot on though :). Could maybe do 'r„ r though if preceeding newlines are fine.

For 23 bytes: .•VvÈ©•¹∍¬„ v:RηεÂ¬ý}.c

@adnan wellp, yeah, but doing it that way would be smart, and that's just not my style ahaha. You want to post it instead? That's a significant improvement over mine to be honest-- barely even looks the same.

The idea is almost exactly the same as your submission, so I don't think I can post this as my own answer. It was the „vr…v r: part that brought up an idea that saves ~6 bytes.

@Adnan fair enough, the lack of the mirror makes it a significant refactor in my eyes though (that and I doubt I'd've got there on my own :P).

@Adnan also Â¬ý is genius... Jeez... You think so differently and it's awesome.

Haskell, 114 110 101 bytes
Thanks to [nimi][1] for -4 13 bytes!
f n=""#(n+1+div n 7)
w#0=[]
w#n|x<-cycle"r vibgyo"!!n=((' '<$[2..n])++reverse w++x:x:x:w):(x:w)#(n-1)

Try it online!

Python 2, 108 bytes
n=input()-1
n+=n/7+2
o=[]
for s in(' vibgyor'*n)[:n]:o=[s+l+s for l in[s]+o]
for l in o:print l.center(n-~n)

Try it online!

R, 130 bytes
function(n,k=n%/%7*8+1+n%%7,a=el(strsplit(' vibgyor'/k,'')))for(i in k:1)cat(d<-' '/(i-1),a[c(k:i,i,i:k)],d,sep='','
')
"/"=strrep

Try it online!

-6 bytes thanks to @JayCe

You can save 6 bytes. Also make you to upvote R's nomination for language of the month :)

@JayCe: thanks ! updated and upvoted !

Jelly, 31 bytes
:7+‘µ“ vibgyor”ṁṚ,Ṛjṛ/ƲƤṭ"ḶṚ⁶ẋƲ

Try it online!
Check out a test suite!
ಠ_ಠ This is overly complicated because Jelly doesn't have a centralize function...

Charcoal, 30 bytes
↶≔… vibgyor⁺²÷×⁸⊖Ｎ⁷θθ⸿Ｅθ✂θκ‖Ｏ←

Try it online! Link is to verbose version of code. Explanation:
↶

Change the drawing direction to upwards.
≔… vibgyor⁺²÷×⁸⊖Ｎ⁷θ

Calculate the height of the rainbow and repeat the literal string to that length.
θ⸿

Print the central line of the rainbow.
Ｅθ✂θκ

Print the right half of the rainbow by taking successive slices and printing each on its own "line".
‖Ｏ←

Reflect to complete the rainbow.

Jelly, 28 bytes
:7+‘“ vibgyor”ṁµṫJZz⁶U;"⁸ŒBṚ

A monadic link accepting an integer which yields a list of lists of characters.
Try it online! (footer joins with newline characters)
Or see the test-suite.
How?
:7+‘“ vibgyor”ṁµṫJZz⁶U;"⁸ŒBṚ - Link: integer
:7                           - integer divide by seven (number of full rainbows)
   ‘                         - increment (the input integer)
  +                          - add (gets the number bands)
    “ vibgyor”               - list of characters = " vibgyor"
              ṁ              - mould like the result above (as a range)
               µ             - start a new monadic chain
                 J           - range of length
                ṫ            - tail (vectorises) (gets the suffixes)
                  Z          - transpose
                   z⁶        - transpose with filler space character
                             -   (together these pad with spaces to the right)
                     U       - reverse each
                             -   (now we have the left side of the rainbow upside down)
                        ⁸    - chain's left argument, as right argument of...
                       "     -   zip with:
                      ;      -     concatenation
                             -   (adds the central character)
                         ŒB  - bounce (vectorises at depth 1)
                             -   (reflects each row like [1,2,3,4] -> [1,2,3,4,3,2,1])
                           Ṛ - reverse (turn the rainbow up the right way)

PowerShell, 108 98 89 85 bytes
param($x)($x+=$x/7-replace'\..*')..0|%{' '*$_+-join(" vibgyor"*$x)[$x..$_+$_+$_..$x]}

Try it online!
This one feels pretty alright now. Banker's rounding is still the devil and I figured out how to make a non-dumb join. I tried monkeying with $ofs to not much success. Speaking of, the results without joins look pretty good, a bit melty:
         vvv
        v     v
       v   rrr   v
      v   r ooo r   v
     v   r o yyy o r   v
    v   r o y ggg y o r   v
   v   r o y g bbb g y o r   v
  v   r o y g b iii b g y o r   v
 v   r o y g b i vvv i b g y o r   v
v   r o y g b i v     v i b g y o r   v

[int]$x+=$x/7 ?

@mazzy That fails for x=25. You have to truncate but casting to int rounds

Yes. And truncate is works

@mazzy I know, the only ways I know to truncate is either [math]::truncate() or the regex trick used above. [int]$x rounds the number. If you know a better way, I'm all ears.

Haskell, 106 113 bytes
I can't yet comment other posts (namely this) so I have to post the solution as a separate answer.
Golfed away 7 bytes by ovs
p x=reverse x++x!!0:x
u m|n<-m+div(m-1)7=[(' '<$[z..n])++p(drop(n-z)$take(n+1)$cycle" vibgyor")|z<-[0..n]]

Try it online!
(Old version, 113 bytes)

Nice answer. I don't know Haskell, but the code seems rather different from the other Haskell answer. PS: That other Haskell answer is actually 110 bytes after the golf-tips in @nimi's comment. Regardless, this is a nice alternative Haskell answer, so +1 from me.

It seems like list comprehensions were the better tool for this challenge. I was able to golf your solution to 106 bytes by reducing the total number of functions. Feel free to adapt these changes.

Python 2, 132 131 bytes
def f(n):
 t=n+n/7;s=('vibgyor '*n)[:t];r=[s[~i:]+t*' 'for i in range(t)]
 for l in zip(*r+3*[' '+s]+r[::-1])[::-1]:print''.join(l)

Try it online!

Saved:

-1 byte, thanks to Jonathan Frech

Why // in Python 2?

@JonathanFrech Because I'm dumb :P

@dzaima, Yeah. Should be fixed now

Red, 153 bytes
func[n][r: take/last/part append/dup copy"""roygbiv "n l: 9 * n + 8 / 8
repeat i l[print rejoin[t: pad/left take/part copy r i l last t reverse copy t]]]

Try it online!
Slightly more readable:
f: func[ n ] [
    r: copy ""
    append/dup r "roygbiv " n
    r: take/last/part r l: 9 * n + 8 / 8
    repeat i l [
        print rejoin [ t: pad/left take/part copy r i l
                       last t
                       reverse copy t ]
    ]
]

Java (JDK 10), 184 bytes
n->{int h=n+n/7,i=h+1,w=i*2+1,j,k=0;var o=new char[i][w];for(;i-->0;o[i][w/2]=o[i][w/2+1])for(j=w/2;j-->0;)o[i][j]=o[i][w+~j]=i<h?j<1?32:o[i+1][j-1]:" vibgyor".charAt(k++%8);return o;}

Try it online!
Prints an extra leading and trailing space for each multiple of 7.
Explanation
n->{                             // IntFunction
 int h=n+n/7,                    //  Declare that height = n + n/7
     i=h+1,                      //          that index  = h + 1
     w=i*2+1,                    //          that width  = (h+1)*2+1
     j,                          //          j
     k=0;                        //          that k      = 0
 var o=new char[i][w];           //  Declare a 2D char array
 for(;                           //  Loop
   i-->0;                        //    Until i is 0
   o[i][w/2]=o[i][w/2+1]         //    After each run, copy the middle letter.
 )
  for(j=w/2;                     //   Loop on j = w/2
   j-->0;                        //     Until j = 0
  )                              //
   o[i][j]                       //    copy letters to the left side,
    =o[i][w+~j]                  //      and the right side
    =i<h                         //      if it's not the last line
     ?j<1                        //        if it's the first (and last) character
      ?32                        //          set it to a space.
      :o[i+1][j-1]               //          else set it to the previous character on the next line.
     :" vibgyor".charAt(k++%8);  //      else assign the next letter.
 return o;                       //  return everything
}

Credits

-2 bytes thanks to Kevin Cruijssen

You can save 2 bytes by changing ,w=-~h*2+1,i=h+1 to ,i=h+1,w=i*2+1

Wow, I should really not golf passed midnight! Thanks for this, @KevinCruijssen! :)

Suggest i-~i instead of i*2+1

Stax, 23 bytes
⌡G'5h!M╩EV[Ez ▼>≈<S⌡⌡0`

Run and debug it
Unpacked, ungolfed, and commented, it looks like this.
" vibgyor"  string literal
,8*7/^      input * 8 / 7 + 1
:m          repeat literal to that length
|]          get all prefixes
Mr          rectangularize, transpose array of arrays, then reverse
            this is the same as rotating counter-clockwise
m           map over each row with the rest of the program, then implicitly output
            the stack starts with just the row itself
  _h        push the first character of the row
  _r        push the reversed row
  L         wrap the entire stack in a single array

Run this one

V (vim), 105 bytes
"aDiaibgyor<esc>0vg_y$@ap0l@alhd$:s/a/ v/g
qqYP0xjYP!!rev
gJkhq2@a@qylpp02ld$0VG:center<c-r>=2*(<c-r>a+ceil(1+<c-r>a/7))

Try it online!
There's many possible saves here, but for now I'm just happy I got it working.


text:
Graph 5-Coloring
Honestly, I can't believe this hasn't already been asked, but here it is
Background
Given a simple undirected planar (the graph can be drawn in the plane without intersections) graph, it is a proven theorem that the graph is 4-colorable, a term we will explore in a bit. However, it's far easier to 5-color a graph, which is what we will focus our challenge on today.
A valid k-coloring of a graph is an assignment of "colors" to the nodes of the graph with the following properties

If two nodes are connected by an edge, the nodes are colored with different colors.
Across the graph, there are a maximum of 5 colors.

Given this, I will present to you a pretty basic algorithm to 5-color any simple undirected planar graph. This algorithm requires the following definitions
Reachability: If node 1 is reachable from node 2, that means that there is a sequence of nodes, each connected to the next by an edge, such that the first node is node 2 and the last is node 1. Note that since undirected graphs are symmetric, if node 1 is reachable from node 2, node 2 is reachable from node 1.
Subgraph: A subgraph of a graph of a given set of nodes N is a graph where the nodes of the subgraph are all in N, and an edge from the original graph is in the subgraph if and only if both nodes being connected by the edge are in N.
Let Color(N) be a function to color planar graphs with N nodes with 5 colors. We define the function below

Find the node with the least number of nodes connected to it. This node will have at most 5 nodes connected to it.
Remove this node from the graph.
Call Color(N-1) on this new graph to color it.
Add the deleted node back to the graph.
If possible, color the added node a color that none of its connected nodes have.
If not possible, then all 5 neighboring nodes to the added node have 5 different colors, so we must try the following process.
Number the nodes surrounding the added node n1...n5
Consider the subgraph of all nodes in the original graph colored the same color as either n1 or n3.
If in this subgraph, n3 is not reachable from n1, in the set of nodes reachable from n1 (including n1), replace all occurrences of n1's color with n3's and vice versa. Now color the added node n1's original color.
If n3 was reachable from n1 in this new graph, do the process from step 9 on nodes n2 and n4, rather than n1 and n3.

Challenge
Given an input of an edgelist (representing a graph), color the graph, by assigning each node a value.
Input: A list of edges in the graph (i.e., [('a','b'),('b','c')...])
Note that the input edgelist will be such that if (a,b) is in the list, (b,a) is NOT in the list.
Output: An object containing pairs of values, where the first element of each pair is a node, and the second its color, i.e.,[('a',1),('b',2)...] or {'a':1,'b':2,...}
You can use anything to represent colors, from numbers, to characters, to anything else.
The input and output is quite flexible, as long as its quite clear what the inputs and outputs are.
Rules

This is a code-golf challenge
You do not have to use the algorithm I've described above. It is simply there for reference.
For any graph, there are often many valid methods of coloring them. As long as the coloring your algorithm produced is valid, that is acceptable.
Remember that the graph must be 5-colored.

Test Cases
Use the following code to test your coloring results validity. As there are many valid graph colorings per graph, this algorithm simply checks the validity of the coloring. See the docstring to see how to use the code.
Some random (and rather silly) test cases:
Test Case 2: Krackhardt Kite Graph
[(0, 1), (0, 2), (0, 3), (0, 5), (1, 3), (1, 4), (1, 6), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6), (5, 7), (6, 7), (7, 8), (8, 9)]
A valid output:
{0: 4, 1: 3, 2: 3, 3: 2, 4: 4, 5: 1, 6: 0, 7: 4, 8: 3, 9: 4}
Note: These test cases are too small to test the more nuanced behavior of the coloring algorithm, so constructing your own graphs is probably a good test of the validity of your work.
Note 2: I'll be adding another piece of code that'll graph your coloring solution soon.
Note 3: I didn't forsee the random coloring algorithms that have been presented, which is what's so cool about PPCG! However, if anyone could golf a more deterministic algorithm, that'd be very cool too.

Aren't the Petersen and the Chvatal graph nonplanar?

How do you feel about taking input as adjacency lists or matrices instead of a list of edges? i.e. instead of [(1, 2), (2, 3), (3, 1)], either { 1: [2, 3], 2: [1, 3], 3: [1, 2]} or [[0, 1, 1], [1, 0, 1], [1, 1, 0]]

@NicHartley Ehh, that's somewhat stretching it I think. That makes the problem noticeably easier

@RushabhMehta I don't see how. It just changes the way you check what's connected to what.

@NicHartley There are well known transpose based operations on adjacency matrices that effectively color graphs. I'll attach a paper when I find one.

I think you would have been better off restricting solutions to polynomial time or requiring a large test case to run successfully in order to force solutions to use graph algorithms like what you seem to have in mind.

@xnor I seem to have learned my lesson. That's alright! Thinking out of the box should be rewarded, not penalized.

"a term we will explore in a bit": don't count on it. A corollary of xnor's observation is that it's rather hard to write a general 4-colouring question which won't be closed as a duplicate of this one. If you're interested in graph theory more broadly, see https://codegolf.meta.stackexchange.com/a/2304/194 for an overview of what has already been covered (and feel free to edit if I've missed a question from the [tag:graph-theory] tag).

@PeterTaylor this is a 5 coloring question

Yes, I know, but a 4-colouring question would have to be designed in such a way that people can't just take their answers to this question, change 5 to 4, and resubmit them.

@PeterTaylor I think my main mistake was that I didn't enforce polynomial time. That would have forced more nuanced approaches

Can we assume the nodes are labeled 1 to n if there are n nodes?

@dylnan That's a no

What are the possible valid labelings for nodes? Can I assume positive integers only or any other restrictions?

@dylnan I was hoping that programs would be flexible enough to handle essentially anything that could be contained in a string, but if it really is a problem, you can assume they will be positive integers

It might not be a problem, but there may be golfing opportunities depending on what we can assume about the input

Python 2, 96 bytes
i=0
g=input()
while 1:i+=1;c={k:i/4**k%4for k in sum(g,())};all(c[s]^c[t]for s,t in g)>0<exit(c)

Try it online!
The input is \$g\$, a list of pairs of integers. We count up \$i\$ from zero, and map natural numbers to graph 4-labelings \$c\$, aborting (and writing \$c\$ to STDERR) as soon as \$c\$ is a valid coloring.
The input is planar, so finding a 4-coloring is always possible.
(Thus: this finds the lexicographically earliest coloring in a sense, and does so very inefficiently.)
The mapping: node \$ k \$ is given color \$ \Big\lfloor \frac{i}{4^k} \Big\rfloor \bmod 4 \$, i.e. the \$k\$’th least significant digit of \$i\$ in base 4.

Nice effort, but I do believe you are missing one component. What about the case where a node is surrounded by 5 different colors?

I'll try to build a test case to break this

Suppose that a given node in your graph is surrounded by 5 other nodes, which you've already colored the 5 colors you are allowed.

My code randomly generates graph colorings and checks them until it generates a correct graph coloring, which it then prints upon exiting. In the case you describe it'd start over and hopefully not color those 5 nodes all 5 available colors.

Ah, I see, I've misunderstood. Interesting approach!

Now it checks all the colorings in lexicographic order :) so it's deterministic and O(5^n), but a lot slower for most inputs.

Well, you can easily improve the speed to $O(4^n)$, no?

JavaScript (ES7), 80 76 74 bytes
Saved 2 bytes thanks to @Neil
Same approach as Lynn. Solves in 4 colors, numbered from 0 to 3.
a=>{for(x=0;a.some(a=>a.map(n=>z=c[n]=x>>n*2&3)[0]==z,c={});x++);return c}

Try it online!

If you're allowed a 4-colouring, then why not x>>n+n&3?

@Neil Ah yes, thanks. I got distracted by the explanation about 5-colouring and forgot the input was guaranteed to be solvable in 4.

Brachylog, 38 bytes
cd{∧4>ℕ}ᶻ.g;?z{tT&h⊇ĊzZhpT∧Zt≠}ᵐ∧.tᵐ≜∧

Try it online!
Explanation
Example input: [["a","b"],["c","b"]]

cd                                       Concatenate and remove duplicates: ["a","b","c"]
  {∧4>ℕ}ᶻ.                               The output is this list zipped zith integers that
                                           are in [0..4]: [["a",I],["b",J],["c",K]]
         .g;?z                           Zip the output with the input:
                                           [[[["a",I],["b",J],["c",K]],["a","b"]],[["a",I],["b",J],["c",K]],["c","b"]]
              {               }ᵐ∧        Map for each element
               tT                        Call T the couple of nodes denoting an edge
                 &h⊇Ċ                    Take a subset of 2 elements in the head
                     zZ                  Zip and call it Z
                      ZhpT               The nodes in Z are T up to a permutation
                          ∧Zt≠           The integers in Z are all different color
                                 .tᵐ≜∧   Label the integers (i.e. colors) in the output so that
                                           it matches the set constraints

Python 2, 211 bytes
def f(g):
 g={k:[(a,b)[a==k]for a,b in g if k in(a,b)]for k in sum(g,())};c={k:0 for k in g}
 for a,b in sorted(g.iteritems(),key=lambda a:len(a[1])):c={k:(c[k],c[k]+1)[c[a]==c[k]and k in b]for k in c}
 return c

Try it online!
Deterministic! Would probably fail on more complicated test cases, but I'm too burnt out to find a graph that it fails for. More test cases and.or criticism welcome!

Clean, 139 bytes
import StdEnv,Data.List
$l#(a,b)=unzip l
#e=nub(a++b)
=hd[zip2 e c\\c<- ?e|all(\(a,b)=c!!a<>c!!b)l]
?[h:t]=[[n:m]\\n<-[0..4],m<- ?t]
?e=[e]

Try it online!
Generates all colorings and returns the first valid one.

Jelly, 23 bytes
®iⱮⱮ³¤ịE€S
FQ©L4ṗÇÐḟḢ®ż

Try it online!
Brute force. Assumes the nodes are labeled by integers.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Divide the work
There is a job which can be decomposed into x equally-sized smaller tasks. You have a team of size y <= x, where every member works equally fast on any task. The goal for this challenge is to divide the work as evenly as possible such that every member of your team has at least 1 task to perform. As evenly as possible means that given any member a, the number of tasks it must perform may be at most one more than any other member b. A single task cannot be further divided or worked on simultaneously by two members.
Input
Your program/function will take as input two positive integers x and y. y is guaranteed to be less than or equal to x. You are free to decide in what order your program will take these inputs. You may take the inputs from any input source desired.
Output
Your program/function will output a list of positive integers of length y representing the number of tasks each member must perform. The list may be in any order. For example, the following outputs are identical:
2 1 2 1
1 1 2 2
2 2 1 1

Outputs may be to any output sink desired.
Examples
Each line pair denotes inputs and one possible output. These example inputs specify x first.
1 1
1

4 1
4

4 2
2 2

4 3
2 1 1

4 4
1 1 1 1

10 3
3 4 3

10 7
1 2 2 2 1 1 1

Scoring
This is code golf; shortest code wins. Standard loopholes apply.

R, 26 bytes
function(x,y)table(1:x%%y)

Try it online!
Counts the number of occurrence of 1,2,...,y in [1...x] modulus y.
12 bytes golfed by @mnel, and than an additional 6 by @digEmAll.

I think this can be reduced to 32 bytes with function(v,w)table(rep(1:w,l=v))

@mnel indeed! We have a number of active golfeRs these days... join the fun :)

Nice approach! I guess this is also valid : 26 bytes

@digEmAll indeed!

JavaScript (ES6), 34 bytes
Takes input as (y)(x).
y=>g=x=>y?[k=x/y--|0,...g(x-k)]:[]

Try it online!
Example for x = 10, y = 3
 Remaining tasks     | # of tasks for next worker | Workers
---------------------+----------------------------+-------------------------------------
 O O O O O O O O O O | 10 / 3 = 3.333... -> 3     | [   O O O ] [ pending ] [ pending ]
 O O O O O O O - - - |  7 / 2 = 3.5      -> 3     | [   O O O ] [   O O O ] [ pending ]
 O O O O - - - - - - |  4 / 1 = 4        -> 4     | [   O O O ] [   O O O ] [ O O O O ]

Haskell, 25 bytes
x#y=map(`div`y)[x..x+y-1]

Try it online!

Python 2, 40 38 36 Bytes
-2 bytes thanks to Mr. Xcoder
lambda x,y:x%y*[x/y+1]+[x/y]*(y-x%y)

Try it Online!

36: lambda x,y:x%y*[x/y+1]+[x/y]*(y-x%y)

Jelly, 3 bytes
sZẈ

Try it online!
How?
sZẈ - Link: integer tasks, integer workers
    - implicit range(tasks)
s   - split into chunks of length workers
 Z  - transpose
  Ẉ - length of each

Jelly, 3 bytes
œsẈ

Try it online!
-1 byte thanks to Jonathan Allan, showing me a built-in I haven't seen before. œs splits the range \$[1 \dots\:x]\$ in \$y\$ similarly sized pieces, then Ẉ retrieves the length of each chunk.

On mobile didn't see other answers already... Ẉ takes this to 3 too

@JonathanAllan Thanks, I wonder how I never saw that built-in.

Only been around for a couple of months I think

Hmm, I've actually used it once but have since forgotten about it. Just edited about 3 answers to with this built-in. Thanks for the heads-up!

C (gcc), 48 bytes
Takes i task size, j team size and returns tasks to array k.
l;f(i,j,k)int*k;{for(l=j;l--;)k[l]=i/j+(i%j>l);}

Try it online!

Brain-Flak, 68 bytes
({}([{}])<{({}(()))}{}>){({}[()]<({}<{({}<>)<>}>()){<>({}<>)}{}>)}{}

Try it online!
Initializes the stack with y ones, then rolls the stack x-y times, each time adding 1 to the former top of the stack.

05AB1E, 7 bytes
LôζðK€g

Try it online or verify all test cases.
L          # Create a list in the range [1, first (implicit) input]
           #  i.e. 10 → [1,2,3,4,5,6,7,8,9,10]
 ô         # Split it in chunks of size second (implicit) input
           #  i.e. [1,2,3,4,5,6,7,8,9,10] and 3 → [[1,2,3],[4,5,6],[7,8,9],[10]]
  ζ        # Zip, swapping rows and columns (with space as filling character by default)
           #  i.e. [[1,2,3],[4,5,6],[7,8,9],[10]] → [[1,4,7,10],[2,5,8,' '],[3,6,9,' ']]
   ðK      # Remove all those spaces
           #  i.e. [[1,4,7,10],[2,5,8,' '],[3,6,9,' ']]
           #   → [['1','4','7','10'],['2','5','8'],['3','6','9']]
     €g    # And then take the length of each inner list as result
           #  i.e. [['1','4','7','10'],['2','5','8'],['3','6','9']] → [4,3,3]

MATL, 6 bytes
:gie!s

Try it online!
(implicit input, y)
:                            % range, push 1...x
g                            % convert to logical (all ones)
i                            % push y
e                            % reshape to matrix of y rows, padding with 0s
!s                           % row sums; as a row vector
(implicit output)

I have created [this meta answer] (https://codegolf.meta.stackexchange.com/a/16802/80010) as a Community wiki so you can modify it.

^ I hope it will let you upvote it after you modify it... otherwise making this a community wiki was a really bad idea!

Haskell, 41 bytes
x#y=[div x y+sum[1|i<=mod x y]|i<-[1..y]]

Try it online!

Java, 55 bytes
By making use of var in Java 10 we can reduce by 1 byte.
y->x->{var a=new int[y];for(;0<x;a[x--%y]++);return a;}

Try it online!
Java 8 Version with 56 bytes
y->x->{int[]a=new int[y];for(;0<x;a[x--%y]++);return a;}

Works by just iterating over the array representing the workers until no tasks are left.

Unless it's explicitly stated otherwise in the question (which it isn't here), you'll need to include private static int[] g(int x, int y) { and the closing brace in your byte count.

Hi, welcome to PPCG! Although @Οurous is indeed right that snippets aren't allowed and it should be either a function or full program, in Java 8+ just y->x->{/*code here*/} would be enough in this case. So it's 55 bytes: y->x->{var a=new int[y];for(;0<x;a[x--%y]++);return a;}. Nice answer though! After you've changed it to comply to the default rules I will upvote it. Enjoy your stay! :)

Oh, and if you haven't done so yet, Tips for golfing in Java and Tips for golving in  might be interesting to read through.

@Οurous Yeah, I missed that, was already late :/

@KevinCruijssen Thanks, I changed that. But with using Lambda it will increase to 62, due to the requirements that lambda parameters have to be effectively final. But thanks :)

@cryoW0lf That's indeed the case when you use x->y->. However, in the code I linked above I use y->x->. :) Only the first of the currying lambda needs to be effectively final, the inner one can be modified. PS: You can remove the space at int[]a in your Java 8 version.

@KevinCruijssen Oh, nice to know, thanks :o

Perl 5 -a, 31 bytes
$a[$_--%$F[1]]++while$_;say"@a"

Try it online!

Groovy, 35 bytes
{x,y->o=[0]*y;while(x--)o[x%y]++;o}

Try it online!

Brachylog, 14 bytes
⟨{h⟦₁}ġ₎t⟩z₁lᵐ

Try it online!
Port of Jonathan Allan's method - range, split, transpose/zip, length - via the explanation in Kevin Cruijssen's answer. Can also be tT&h⟦₁;Tġ₎z₁lᵐ equivalently.
Another neat answer is:
19 bytes
h~+.ℕ₁ᵐ≜⟨⌉-⌋⟩<2&t~l

Try it online!

UGL 1.0.0, 20 Bytes
CÑORCPFÐWC_+_WNINI

Port of the Haskell answer. (even though the language transpiles to Python)
Takes 2 inputs via stdin.
Explanation (Warning: This may get out of hand)(update: it did not)
C takes two arguments, and apart from some other functions, it is (lambda x,y:map(x,y)).
Ñ is the alias of the int() function. (When you pass it as parameter instead of feeding arguments to it)
O takes one function with two arguments, and two anything, and applies the function to them.
R defines a lambda with two arguments: lambda _,W: <stuff>
C, again is map.
P is functools.partial
F is flip (lambda f: lambda x,y: f(y,x))
Ð is the alias of Division (/)
W is the second argument of the lambda we defined with R
C is exclusive range this time
_ is the first argument of the lambda we defined with R
+_W is literally _+W
NINI is two inputs taken from stdin and converted to integers.
So, this thing is (functions redefined in order to make the last line a bit short):
import functools as ft
apply2 = lambda x,y,z: x(y,z)
flip = lambda f: lambda x,y: f(y,x)
div = lambda x,y: x/y
rg = range
p = print
ip = input()
p(map(int,apply2(lambda _,W: map(ft.partial(flip(div),W),rg(_,(_+W))),int(ip()),int(ip()))))

Lua, 50 49 bytes
1 byte saved thanks to DLosc :)
x,y=...repeat print(x//y)x=x-x//y y=y-1until y<=0

Try it online!

The output is decimal and in different lines because of the way Lua implements the function print(), if this is a problem I can edit the submission to use io.write() instead.

1 byte savings is possible by eliminating the space between 1 and until. :)

Clean, 39 bytes
Not much room for originality in this one.
import StdEnv
$x y=[i/y\\i<-[x..x+y-1]]

Try it online!
Defines the function $ :: Int Int -> [Int], always returning higher numbers towards the end.

Charcoal, 19 bytes
ＮθＮηＩＥθ⁻÷×⊕ιηθ÷×ιηθ

Try it online! Link is to verbose version of code. Based on Bresenham's line algorithm. Explanation:
Ｎθ                  Input team size
  Ｎη                Input number of tasks
      θ             Team size
     Ｅ              Map over implicit range
           ι    ι   Current value
          ⊕         Incremented
            η    η  Number of tasks
         ×     ×    Multiply
             θ    θ Team size
        ÷     ÷     Integer divide
       ⁻            Subtract
    Ｉ               Cast to string
                    Implicitly print

APL (Dyalog), 19 bytes
4 bytes saved thanks to @Adám
{×⍵:(⍺-1)∇⍵-⎕←⌊⍵÷⍺}

Try it online!

0=⍵:⋄ → ×⍵:

Can't you remove k←?

@Adám thanks, gone a bit rusty :P

Forth (gforth), 47 bytes
: f tuck /mod swap rot 0 do 2dup i > - . loop ;

Try it online!
Explanation
Divides the work by the number of people, add 1 to all workers whose index is less than (or equal) to the amount of excess work (the remainder/modulus)
Code Explanation
: f            \ start a new word definition
  tuck         \ stick a copy of the number of workers in the "back" of the stack
  /mod swap    \ get the quotient and remainder, move remainder to the top
  rot          \ grab the copy of the number of workers from earlier and move it to the top
  0 do         \ start counted loop from 0 to #workers - 1
    2dup       \ duplicate the modulus and minimum work
    i >        \ check if the index is greater than the remainder
    -          \ subtract from minimum work (forth uses -1 for "true")
    .          \ output the result
  loop         \ end the counted loop
;              \ end the word definition

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
The Onion, or Not The Onion?
The Onion (warning: many articles are NSFW) is a satirical news organization that parodies traditional news media. In 2014, The Onion launched ClickHole (warning: also frequently NSFW), a satirical news website that parodies "clickbait" sites like BuzzFeed. Thanks to Poe's Law, it's fairly common for people to read the headlines of articles from The Onion or ClickHole and believe them to be true, not knowing that they are intended to be satire. The converse also happens with ridiculous-sounding real news stories - people often think that they are satire when they are not.
This confusion naturally lends itself to a game - given a news headline, try to guess whether or not it is satire. This challenge is about doing exactly that with a program.
Given a news headline (a string consisting of only printable ASCII characters and spaces), output 1 if the headline is satire, or 0 if it is not. Your score will be the number of correct outputs divided by the total number of headlines.
As per usual, standard loopholes (especially optimizing for the test cases) are not allowed. To enforce this, I will run your programs on a set of 200 hidden test cases (100 from The Onion, 100 from Not The Onion). Your solution must score no more than 20 percentage points less than your score on the public test cases in order to be valid.
Test Cases
To come up with test cases for this challenge, I picked 25 headlines from The Onion subreddit (where articles from The Onion and its child sites, like ClickHole, are posted), and 25 headlines from the Not The Onion subreddit (where real news articles that sound like satire are posted). The only changes I made to the headlines were replacing "fancy" quotes with regular ASCII quotes and standardizing capitalization - everything else is left unchanged from the original article's headline. Each headline is on its own line.
The Onion headlines
Trump Warns Removing Confederate Statues Could Be Slippery Slope To Eliminating Racism Entirely
'No Way To Prevent This,' Says Only Nation Where This Regularly Happens
My Doctor Told Me I Should Vaccinate My Children, But Then Someone Much Louder Than My Doctor Told Me I Shouldn't
Man At Park Who Set Up Table Full Of Water Cups Has No Idea How Passing Marathon Runners Got Impression They Can Take Them
This Child Would Have Turned 6 Today If His Mother Hadn't Given Birth To Him In October
Incredible Realism: The Campaign In The Next 'Call Of Duty' Will Begin At Your Avatar's High School Cafeteria When He's Being Tricked Into Joining The Military By A Recruiter
'Sometimes Things Have To Get Worse Before They Get Better,' Says Man Who Accidentally Turned Shower Knob Wrong Way
Report: Uttering Phrase 'Easy Does It' Prevents 78% Of Drywall Damage While Moving Furniture
Barbara Bush Passes Away Surrounded By Loved Ones, Jeb
Family Has Way Too Many Daughters For Them Not To Have Been Trying For Son
News: Privacy Win! Facebook Is Adding A 'Protect My Data' Button That Does Nothing But Feels Good To Press
Dalai Lama Announces Next Life To Be His Last Before Retirement
Researchers Find Decline In Facebook Use Could Be Directly Linked To Desire To Be Happy, Fully Functioning Person
Manager Of Combination Taco Bell/KFC Secretly Considers It Mostly A Taco Bell
Trump: 'It's My Honor To Deliver The First-Ever State Of The Union'
Daring To Dream: Jeff Bezos Is Standing Outside A Guitar Center Gazing Longingly At A $200 Billion Guitar
Area Dad Looking To Get Average Phone Call With Adult Son Down To 47.5 Seconds
Experts Warn Beef Could Act As Gateway Meat To Human Flesh
Jeff Bezos Named Amazon Employee Of The Month
Dad Suggests Arriving At Airport 14 Hours Early
Report: Only 3% Of Conversations Actually Need To Happen
Delta Pilot Refuses To Land Until Gun Control Legislation Passed
Family Wishes Dad Could Find Healthier Way To Express Emotions Than Bursting Into Full-Blown Musical Number
New Honda Commercial Openly Says Your Kids Will Die In A Car Crash If You Buy A Different Brand
Teacher Frustrated No One In Beginner Yoga Class Can Focus Chakras Into Energy Blast

Not The Onion headlines
Man Rescued From Taliban Didn't Believe Donald Trump Was President
Nat Geo Hires Jeff Goldblum To Walk Around, Being Professionally Fascinated By Things
Mike Pence Once Ratted Out His Fraternity Brothers For Having A Keg
Reddit CEO Tells User, "We Are Not The Thought Police," Then Suspends That User
Trump Dedicates Golf Trophy To Hurricane Victims
Uber's Search For A Female CEO Has Been Narrowed Down To 3 Men
ICE Director: ICE Can't Be Compared To Nazis Since We're Just Following Orders
Passenger Turned Away From Two Flights After Wearing 10 Layers Of Clothing To Avoid Luggage Fee
Somali Militant Group Al-Shabaab Announces Ban On Single-Use Plastic Bags
UPS Loses Family's $846k Inheritance, Offers To Refund $32 Shipping Fee
Teen Suspended From High School After Her Anti-Bullying Video Hurts Principal's Feelings
Alabama Lawmaker: We Shouldn't Arm Teachers Because Most Are Women
Cat Named After Notorious B.I.G. Shot Multiple Times - And Survives
EPA Head Says He Needs To Fly First Class Because People Are Mean To Him In Coach
Apology After Japanese Train Departs 20 Seconds Early
Justin Bieber Banned From China In Order To 'Purify' Nation
Alcohol Level In Air At Fraternity Party Registers On Breathalyzer
NPR Tweets The Declaration Of Independence, And People Freak Out About A 'Revolution'
Man Who Mowed Lawn With Tornado Behind Him Says He 'Was Keeping An Eye On It.'
After Eating Chipotle For 500 Days, An Ohio Man Says He's Ready For Something New
'El Chapo' Promises Not To Kill Any Jurors From Upcoming Federal Trial
After 4th DWI, Man Argues Legal Limit Discriminates Against Alcoholics
Palestinian Judge Bans Divorce During Ramadan Because 'People Make Hasty Decisions When They're Hungry'
Argentinian Officers Fired After Claiming Mice Ate Half A Ton Of Missing Marijuana
'Nobody Kill Anybody': Murder-Free Weekend Urged In Baltimore

Sandbox

Your score will be the number of correct outputs divided by the total number of headlines Is bytecount a tie breaker?

I'm a little bit confused. What kind of solution do you expect? Every solution is going to have to "optimize for the test cases" somewhat, bar writing an AI that can understand English and has a sense for humor. For example, Arnauld's solution detects /ly\b/ which works only because the 25 Onion headlines you picked happen to have more adverbs, but for all I know you could easily trip it up with a different test battery. And who's to say his coefficients aren't chosen to optimize his score? (Why wouldn't he optimize them?)

Is querying a search API (for example Google), considered a loophole?

@Night2 Yes, because that's fetching the result from an external source.

@Mego I feel like we'd do better if we had the body text as well, since the sarcasm comes off a lot more easily there

@RushabhMehta That would be a different challenge

@Lynn I think it's a safe assumption that these test cases are representative of the entire set of all headlines.  Therefore, finding a pattern like -ly and extrapolating that that would hold with additional test cases seems fair to me.

This test battery does seem a bit unusual. It's like asking for a classifier that can detect dogs in a photograph, but taking your positive test cases as photos of dogs and your negative test cases from a Buzzfeed article titled "25 Photos of Objects You'll Swear Are Dogs, But Nope, Turns Out They Aren't! (#11 Will Blow Your Mind!)" It makes a hard enough problem harder.

Not only is the challenge hard, but it's also non-obvious (to me) what's the difference. If I can't solve it, of course my program can't solve it (that is, while convince me that it doesn't hardcode for the test cases)

Well I spent +36 hours training an artificial neural network using brain.js and LSTM, with samples in this issue and 100 other samples of each type from provided links, but the result wasn't good enough with new titles which weren't present in training sets. I'm done :P

@Skidsdev Tiebreaker is the default - the first answer (by edit time) to reach the tied score.

JavaScript (ES7), 39 / 50 (78%)
63.5% (127/200) on hidden test cases
A simple heuristic based on the length of the title, number of spaces and use of the -ly suffix.
isOnion = str =>
  str.length ** 0.25 +
  str.split(' ').length ** 1.25 * 2 +
  str.split(/ly\b/).length ** 1.75 * 7
  > 76

Try it online!

This is absurdly effective for how simple it is.

This solution scored 63.5% on the hidden test cases, so it is valid.

Not as simple as was possible in the beginning of the sandbox (100%, utilizing capitalization differences before it was standardized) but this is really simple.

@Mego Just out of curiosity, does this NSFW version improve the score on the hidden test cases? :)

@Arnauld 66% with that version

Python 3, 84%
Untested on hidden test cases.
This uses Keras LSTM RNN trained on various headlines. To run it you need Keras the following and the model which I've made available on GitHub: repo link. You will need the model .h5 and the word/vector mappings are in .pkl. The latest
The dependencies are:
import numpy as np
from pickle import load
from keras.preprocessing import sequence, text
from keras.models import Sequential
from keras.layers import Dense, Embedding, SpatialDropout1D, LSTM, Dropout
from keras.regularizers import l2
import re

The settings are:
max_headline_length = 70
word_count = 20740

The model is:
model = Sequential()
model.add(Embedding(word_count, 32, input_length=max_headline_length))
model.add(SpatialDropout1D(0.4))
model.add(LSTM(64, kernel_regularizer=l2(0.005), dropout=0.3, recurrent_dropout=0.3))
model.add(Dropout(0.5))
model.add(Dense(32, kernel_regularizer=l2(0.005)))
model.add(Dropout(0.5))
model.add(Dense(2, kernel_regularizer=l2(0.001), activation='softmax'))

Now to load the model and the word embeddings:
model.load_weights('model.h5')
word_to_index = load(open('words.pkl', 'rb'))

And the code to test if a string is from 'NotTheOnion' or 'TheOnion' I've written a quick helper function which converts the string to the respective word embeddings:
def get_words(string):
  words = []
  for word in re.finditer("[a-z]+|[\"'.;/!?]", string.lower()):
    words.append(word.group(0))
  return words

def words_to_indexes(words):
  return [word_to_index.get(word, 0) for word in words]

def format_input(word_indexes):
  return sequence.pad_sequences([word_indexes], maxlen=max_headline_length)[0]

def get_type(string):
  words = words_to_indexes(get_words(string))
  result = model.predict(np.array([format_input(words)]))[0]

  if result[0] > result[1]:
    site = 'NotTheOnion'
  else:
    site = 'TheOnion'

  return site

Explanation
This code runs a model which analyzes the relationships between words by representing the words as a 'vector'. You can learn more about word embedding here.
This is trained on headlines but the test cases are excluded.
This processes is automated after a quite a bit of processing. I've distributed the final processed word list as a .pkl but what happens in word embedding is first we analyze the sentence and isolate the words.
After we now have the words the next step is to be able to understand the differences and similarities between certain words e.g. king and queen versus duke and duchess. These embeddings don't happen between the actual words but between numbers representing the words which is what is stored in the .pkl file. Words that the machine doesn't understand are mapped to a special word <UNK> which allows us to understand that there is a word there but that it is not known exactly what the meaning is.
Now that the words are able to be understood, the sequence of words (headline) needs to be able to be analyzed. This is what 'LSTM' does, an LTSM is a type of 'RNN' cell which avoids the vanishing gradient effect. More simply, it takes in a sequence of words and it allows us to find relationships between them.
Now the final layer is Dense which basically means it's kind of like an array meaning the output is like: [probability_is_not_onion, probability_is_onion]. By finding which one is larger we can choose which one is the most confident result for the given headline.

Python 3 + Keras, 41/50 = 82%
83% (166/200) on hidden test cases
import json
import keras
import numpy
import re

from keras import backend as K

STRIP_PUNCTUATION = re.compile(r"[^a-z0-9 ]+")

class AttentionWeightedAverage(keras.engine.Layer):
    def __init__(self, return_attention=False, **kwargs):
        self.init = keras.initializers.get("uniform")
        self.supports_masking = True
        self.return_attention = return_attention
        super(AttentionWeightedAverage, self).__init__(**kwargs)

    def build(self, input_shape):
        self.input_spec = [keras.engine.InputSpec(ndim=3)]
        assert len(input_shape) == 3

        self.W = self.add_weight(shape=(input_shape[2], 1),
                                 name="{}_W".format(self.name),
                                 initializer=self.init)
        self.trainable_weights = [self.W]

        super(AttentionWeightedAverage, self).build(input_shape)

    def call(self, x, mask=None):
        logits = K.dot(x, self.W)
        x_shape = K.shape(x)
        logits = K.reshape(logits, (x_shape[0], x_shape[1]))

        ai = K.exp(logits - K.max(logits, axis=-1, keepdims=True))

        if mask is not None:
            mask = K.cast(mask, K.floatx())
            ai = ai * mask

        att_weights = ai / (K.sum(ai, axis=1, keepdims=True) + K.epsilon())
        weighted_input = x * K.expand_dims(att_weights)

        result = K.sum(weighted_input, axis=1)

        if self.return_attention:
            return [result, att_weights]

        return result

    def get_output_shape_for(self, input_shape):
        return self.compute_output_shape(input_shape)

    def compute_output_shape(self, input_shape):
        output_len = input_shape[2]

        if self.return_attention:
            return [(input_shape[0], output_len), (input_shape[0], input_shape[1])]

        return (input_shape[0], output_len)

    def compute_mask(self, input, input_mask=None):
        if isinstance(input_mask, list):
            return [None] * len(input_mask)
        else:
            return None

if __name__ == "__main__":
    model = keras.models.load_model("combined.h5", custom_objects={"AttentionWeightedAverage": AttentionWeightedAverage})
    with open("vocabulary.json", "r") as fh:
        vocab = json.load(fh)

    while True:
        try:
            headline = input()
        except EOFError:
            break

        tokens = STRIP_PUNCTUATION.sub("", headline.lower()).split()

        inp = numpy.zeros((1, 45))

        for i, token in enumerate(tokens):
            try:
                inp[0,i] = vocab[token]
            except KeyError:
                inp[0,i] = 1

        print(model.predict(inp)[0][0] > 0.3)

combined.h5 and vocabulary.json can be retrieved from here (very large) and here.
Fully-connected classifier connected to a pre-trained sentiment analysis model DeepMoji, which consists of stacked bi-directional LSTMs and an attentional mechanism. I froze the DeepMoji layers and took out the final softmax layer, trained just the fully connected layers, then unfroze the DeepMoji layers and trained them together for finetuning. The attentional mechanism is taken from https://github.com/bfelbo/DeepMoji/blob/master/deepmoji/attlayer.py (I didn't want to have to use all their code as a dependency for one class, especially since it's Python 2 and rather unwieldy to use as a module...)
This performs surprisingly poorly on Mego's test set, considering that on my own larger validation set it gets >90%. So I'm not done with this yet.

83% on hidden test cases, assuming I ran it correctly

JavaScript (Node.js), 98% (49/50)
96% (192/200) on hidden test cases
const words = require('./words');
const bags = require('./bags');

let W = s => s.replace(/[^A-Za-z0-9 ]/g, '').toLowerCase().split(' ').filter(w => w.length > 3);

let M = b => {
    for (let i = 0; i < bags.length; i++) {
        let f = true;
        for (let j = 0; j < bags[i].length; j++) if (!b.includes(bags[i][j])) {
            f = false;
            break;
        }
        if (f) return true;
    }
    return false;
};

let O = s => {
    let b = [];
    W(s).forEach(w => {
        let p = words.indexOf(w);
        if (p >= 0) b.push(p);
    });
    return (b.length > 0 && M(b));
};

This requires two large JSON files which I can't put them here or on "TiO". Please download them from the following links and save them with the words.json and bags.json names, in the same folder as JS file. There is also a link for a JS file with test cases and result/percent printing. You can put your hidden test cases in onions and nonOnions variables.

words.json
bags.json
onion.js (this includes default test cases)

After saving all 3 files in same directory, run node onion.js.
The O function will return true if it is onion and false if it isn't. Uses a big list of word bags (without order) to detect if the input string is onion. Kind of hard coded, but works very well on a variety of random test cases.

This solution gets 96% on the hidden test cases

Working off Arnauld's solution
JavaScript (ES6), 41 / 50
64% (128/200) on hidden test cases
str.includes("Dad") || str.length ** .25 +
  str.split(' ').length ** 1.25 * 2 +
  str.split(/ly\b/).length ** 1.75 * 7
 > 76

JavaScript (ES6), 42 / 50
62.5% (125/200) on hidden test cases (invalid)
isOnion = str =>
  str.includes("Dad") || str.length ** .25 +
  str.split(' ').length ** 1.25 * 2 +
  str.split(' ').filter(w => w.length > 3 && w.split(/ly/).length > 1).length * 23.54 +
 /\d/.test(str) * 8
 > 76

The length+word count+"ly " concept works pretty well,  I was able to squeeze a few more points out by checking for the word "Dad" (when do real articles talk about people's dads in the third person in the title?) and an additional point by changing the "ly " search heuristic and checking for the presence of numbers in the title (which might be less valid in the general case outside the test, so I left both solutions)

I don't know about the dad part...seems a little bit like optimizing the test case to me...

And yes, I can find plenty of Not the Onion articles mentioning dads

There's probably a better way to do it as part of the heuristic and not just a hard "win" if it contains dad, but I imagine even outside the test database abstractly talking about a specific "Dad" is more common on The Onion

Your first solution scored 64% on the hidden test cases, so it is valid. Your second solution scored 62.5% on the hidden test cases, so it is not valid.

@Mego What a close margin...


text:
Sequentia Filii Bonacci
Leonardo of Pisa (ca. 1175 - ca. 1245) is better known as Fibonacci. But this is actually a short for the Latin "filius Bonacci" (the son of Bonacci) which was made up during the 18th century (according to Wikipedia).
In this challenge, you'll be given an ordinal number (in the literal sense) between 1st and 20th and you have to return the corresponding term in the Fibonacci sequence.
The twist is that the ordinal number will be given in Latin.
Example: "duodecimus" → \$89\$.
Full I/O table
 input              | meaning | output
--------------------+---------+--------
 "primus"           |   1st   |    0
 "secundus"         |   2nd   |    1
 "tertius"          |   3rd   |    1
 "quartus"          |   4th   |    2
 "quintus"          |   5th   |    3
 "sextus"           |   6th   |    5
 "septimus"         |   7th   |    8
 "octavus"          |   8th   |   13
 "nonus"            |   9th   |   21
 "decimus"          |  10th   |   34
 "undecimus"        |  11th   |   55
 "duodecimus"       |  12th   |   89
 "tertius decimus"  |  13th   |  144
 "quartus decimus"  |  14th   |  233
 "quintus decimus"  |  15th   |  377
 "sextus decimus"   |  16th   |  610
 "septimus decimus" |  17th   |  987
 "duodevicesimus"   |  18th   | 1597
 "undevicesimus"    |  19th   | 2584
 "vicesimus"        |  20th   | 4181

Rules

The input is guaranteed to be exactly one of the strings described above.
If that helps, you may take it in full uppercase instead. But it must be consistent for all entries. Mixed cases are not allowed.
Depending on your algorithm and language, hardcoding or computing the terms of the sequence may either win or lose bytes. Both approaches are explicitly allowed.
This is code-golf!

Fun fact: there is a https://latin.stackexchange.com/

R, 91 86 bytes
Look up the index of the sum of bytes in a brute-forced UTF8 lookup table and use the magic Fibonacci generating function to give the answer.
function(x)round(1.618^match(sum(!x)%%93,!'%(-1!5+3JOSCW6')*.2765)
"!"=utf8ToInt

Try it online!
Edit: -2 bytes by improved numeric rounding
Edit: -3 bytes with a change to the lookup (thanks for the hint, @Giuseppe!)

Wanted to do something similar with UTF8 lookup. Had no clue you could Fibonnaci like that. probably shorter than what I wanted to do (chartr the UTF8 of the sum with the UTF8 of the fibonacci value, and then intToUtf8 the output of chartr.

90 bytes

Seems to fail for "sextus decimus", Giuseppe.

@J.Doe huh well alright then. no idea what happened there, as it's the only one that's wrong!

You were onto the right thing @Giuseppe, turned out there were 3 magic 2-digit moduli for which the sum of bytes was unique, 69, 88 and 93, and 88 was the one which didn't need any constant added to make an intelligible string.

Sometimes I feel like half of codegolf is finding the right number use as the modulus...

Clean, 87 bytes
All escapes except \n are treated as one byte, since the compiler's fine with the actual raw values. (TIO and SE have issues with it not being valid UTF-8 though, and so it's escaped here)
FryAmTheEggman made a nice demonstration / workaround: here
import StdEnv
$s=hd[i\\i<-k 1 0&c<-:"\340\152\060\065\071\354\172\045\223\n\255\362\132\137\143\026\244\051\344\270"|c==sum s]
k b a=[a:k(a+b)b]

Try it online!
Defines the function $ :: [Char] -> Int, which uses the uniqueness in the summation of the uppercase character values to determine which term in the sequence (generated by the helper function k) to return.

Ruby, 104 93 bytes
->x{[8,4181,3,144,21,13,0,1,233,5,987,0,377,55,0,89,1,1597,34,610,0,2,2584][x.sum%192%76%23]}

Try it online!
Simply takes the sum of the bytes, modulo 192 modulo 76 modulo 23, and indexes into a lookup table. (Magic numbers found by brute force.)

6502 machine code (C64), 82 bytes
00 C0 20 9E AD 20 A3 B6 A8 88 A9 05 4A 90 02 49 B1 71 22 88 10 F6 29 1F C9 07
B0 02 69 0D A8 BE 32 C0 B9 1E C0 4C CD BD 00 00 00 00 03 00 0A 00 06 10 01 00
FF 00 02 00 00 00 00 00 08 00 15 0D DB 02 18 90 3D 55 79 05 FF E9 62 22 01 59
01 37 FF 03

This uses hashing (of course), but optimized for short implementation on the 6502, taking advantage of the carry flag set by shifting and used in addition. Magic numbers for hashing were found by brute forcing with a little C program; the FF bytes are unfortunate holes in the hash table ;)
Byte count: 2 bytes load address, 38 bytes code, 42 bytes hashtable for values.
Online demo
Usage: SYS49152"[ordinal]", for example SYS49152"DUODECIMUS". (note the letters appear upper case in the default C64 configuration).
Important: Before the first start, issue a NEW command. This is needed because the C64 BASIC LOAD command fiddles with some BASIC vectors, even when loading a machine program to some absolute address (like here $C000/49152).
Commented disassembly:
         00 C0                          ; load address
.C:c000  20 9E AD    JSR $AD9E          ; evaluate expression
.C:c003  20 A3 B6    JSR $B6A3          ; evaluate as string
.C:c006  A8          TAY                ; length to y register
.C:c007  88          DEY                ; decrement (start at last char)
.C:c008  A9 05       LDA #$05           ; start value for hash
.C:c00a   .hashloop:
.C:c00a  4A          LSR A              ; shift right
.C:c00b  90 02       BCC .skip          ; shifted bit zero? -> skip xor
.C:c00d  49 B1       EOR #$B1           ; xor "magic" value
.C:c00f   .skip:
.C:c00f  71 22       ADC ($22),Y        ; add current character (plus carry)
.C:c011  88          DEY                ; previous character
.C:c012  10 F6       BPL .hashloop      ; pos >= 0? -> repeat
.C:c014  29 1F       AND #$1F           ; mask lowest 5 bits
.C:c016  C9 07       CMP #$07           ; larger than 7 ?
.C:c018  B0 02       BCS .output        ; -> to output
.C:c01a  69 0D       ADC #$0D           ; add 13
.C:c01c   .output:
.C:c01c  A8          TAY                ; hash to y register
.C:c01d  BE 32 C0    LDX .lb-8,Y        ; load low byte from hashtable
.C:c020  B9 1E C0    LDA .hb-8,Y        ; load high byte from hashtable
.C:c023  4C CD BD    JMP $BDCD          ; to output of 16bit number
.C:c026   .hb:
.C:c026  00 00 00 00 .BYTE $00,$00,$00,$00
.C:c02a  03 00 0A 00 .BYTE $03,$00,$0A,$00
.C:c02e  06 10 01 00 .BYTE $06,$10,$01,$00
.C:c032  FF 00 02 00 .BYTE $FF,$00,$02,$00
.C:c036  00 00 00 00 .BYTE $00,$00,$00,$00
.C:c03a   .lb:
.C:c03a  08 00 15 0D .BYTE $08,$00,$15,$0D  ; second byte used in .hb as well
.C:c03e  DB 02 18 90 .BYTE $DB,$02,$18,$90
.C:c042  3D 55 79 05 .BYTE $3D,$55,$79,$05
.C:c046  FF E9 62 22 .BYTE $FF,$E9,$62,$22
.C:c04a  01 59 01 37 .BYTE $01,$59,$01,$37
.C:c04e  FF 03       .BYTE $FF,$03

C64 BASIC V2 test suite
(containing the machine program in DATA lines)
Online demo
0fOa=49152to49231:rEb:pOa,b:nE
1?"primus",:sY49152"primus":?
2?"secundus",:sY49152"secundus":?
3?"tertius",:sY49152"tertius":?
4?"quartus",:sY49152"quartus":?
5?"quintus",:sY49152"quintus":?
6?"sextus",:sY49152"sextus":?
7?"septimus",:sY49152"septimus":?
8?"octavus",:sY49152"octavus":?
9?"nonus",:sY49152"nonus":?
10?"decimus",:sY49152"decimus":?
11?"undecimus",:sY49152"undecimus":?
12?"duodecimus",:sY49152"duodecimus":?
13?"tertius decimus",:sY49152"tertius decimus":?
14?"quartus decimus",:sY49152"quartus decimus":?
15?"quintus decimus",:sY49152"quintus decimus":?
16?"sextus decimus",:sY49152"sextus decimus":?
17?"septimus decimus",:sY49152"septimus decimus":?
18?"duodevicesimus",:sY49152"duodevicesimus":?
19?"undevicesimus",:sY49152"undevicesimus":?
20?"vicesimus",:sY49152"vicesimus":?
21dA32,158,173,32,163,182,168,136,169,5,74,144,2,73,177,113,34,136,16,246,41,31
22dA201,7,176,2,105,13,168,190,50,192,185,30,192,76,205,189,0,0,0,0,3,0,10,0,6
23dA16,1,0,255,0,2,0,0,0,0,0,8,0,21,13,219,2,24,144,61,85,121,5,255,233,98,34,1
24dA89,1,55,255,3

C (gcc), 135 129 bytes
6 bytes down by suggestion of ceilingcat and Logern
f;i;b;o;n(char*a){for(f=i=b=o=0;*a;o+=21*b+++*a++-70);for(b=1,o="TACIHAAJQFSAAARCAMGKDANPEAOAAL"[o%30];--o>65;f=b,b=i)i=f+b;a=i;}

Try it online!
Explanation:
f; i; b; o; // Variables

n (char *a)
{
     // Calculate a silly hash of incoming string
     for (f = i = b = o = 0; *a; o += 21 * b++ + *a++ - 70);

     // Use the hash to index into the array of number values
     // and calculate the corresponding Fibonacci sequence element
     for
     (
         b = 1,
         o = "TACIHAAJQFSAAARCAMGKDANPEAOAAL"[o % 30];

         --o > 65;
         f = b, b = i
     )
         i = f + b;

     // implicit return
     a = i;
}

You can replace return i; with a=i;

Perl 6, 62 bytes
{(0,1,*+*...*)[index '%(-1!5+3JOSCW6',chr .ords.sum%93]}

Try it online!
Uses a lookup table in a string, as well as a short fibonacci sequence generator.

Pyth, 54 bytes
L?>b1+ytbyttbbyxc."axnÛ±r†XVW‹(„WîµÏ£"2+hQ@Q618

Test suite
Notice: as the code makes use of some unprintable characters, it may not display correctly on Stack Exchange. The link provided leads to a working and copy-pastable source.
Long story short, Q[0]+Q[618%len(Q)] gives unique results for all accepted inputs Q.

Python 2, 292 bytes
f=lambda x:x>1and f(x-1)+f(x-2)or x
def g(t):
	for i,c in zip("pr secun ter qua qui sex sep oc no ec".split(),range(1,11))+zip("un duo es ev".split(),(1,2,20,"-")):t=t.replace(i,str(c))
	return f(abs(eval("+".join("".join((" ",c)[c in"0123456789-"]for c in t).split()).replace("+-+","-")))-1)

Try it online!
Fibonacci generator shamelessly stolen from this answer.
Breaks each word down into its meaningful component parts and discards the rest (in "duodevicesimus", for example, we only care about "duo ev  es    "-> "2 -  20    " - > abs("2-20") -> 18).
Passes the calculated value (minus 1 to 0-offset) to the Fibonacci generator function.
Ungolfed Explanation:
# Fibonacci function
f=lambda x:x>1and f(x-1)+f(x-2)or x

def g(t):
    # generates a list of key, value pairs like [("pr", 1, ..., ("ec", 10)] +
    values = zip("pr secun ter qua qui sex sep oc no ec".split(), range(1,11))

    # adds values to existing list
    values += zip("un duo es ev".split(),(1,2,20,"-"))

    # replace the matching values in the string with the appropriate number/sign.
    # ORDER MATTERS - if "un" is searched for before "secun", this generates incorrect values.
    for i,c in values:
        t = t.replace(i,str(c))

    # replace each non-digit, non-minus character in string with "c"
    t = [(" ",c)[c in"0123456789-"]for c in t]

    # convert space-replaced array back to a string
    # then split it on spaces, creating an array of values
    t = "".join(t).split()

    # turn the array back into a string, with each individual item separated by "+"
    # this will cause "-" to become "+-+" (since "-" is ALWAYS between two numbers), so prelace that sequence with "-"
    t = "+".join(t).replace("+-+","-")

    # evaluate the string as an expression, and take the absolute value for when - occurs
    t = abs(eval(t))

    # pass the value, minus 1 for 0-offset, to the Fibonacci function.
    return f(t-1)

Python 2, 97 79 bytes
lambda s:int(1.618**('RV3NJ^[KDP=Z62AWeG<C'.find(chr(hash(s)%69+48)))*.4474+.5)

Try it online!
First, we want to convert from latin to a number n; this is accomplished by replicating the input string enough times to ensure that there are at least 11 characters total; and then the 3rd and 10th characters (zero indexed) form a unique pair taking the hash mod 69 and turning that into a printable char.
Now we have n. To find the nth Fibonacci number, we can use the rounding method, using only as many digits of precision as we need up to Fib(20).

JavaScript (Node.js), 100 97 95 92 91 bytes
x=>1.618**(p=parseInt)("1 jgf7  ei 490dbch62385a"[p(x.length+x,32)%12789%24],36)*.4474+.5|0

Try it online!
Warning: WORKS BECAUSE OF FLOATING POINT INACCURACY
JavaScript has neither a built-in hash function, nor a short enough character-to-ASCII function (String.charCodeAt is the shortest already), so I need to define a simple hash function by myself.
Used the same rounding method as Chas Brown did after calculating the hash.
After a whole day of brute-forcing a better is found:
b32_to_dec(x.length + x) % 12789 % 24 (*floating point inaccuracy)
b32_to_dec(x.length + x) % 353 % 27 (*floating point inaccuracy)
b36_to_dec(x.length + x[2]) % 158 % 29 - 4
b36_to_dec(x[2] + x.length) % 741 % 30
b36_to_dec(x[0] + x[2] + x.length) % 4190 % 27
parseInt(x.length + x, 32) result
primus 7310236636
secundus 9773632960476
tertius 272155724764
quartus 269453490140
quintus 269461747676
sextus 7054
septimus 9774067964892
octavus 266721394652
nonus 192700380
decimus 254959770588
undecimus 350449413217244
duodecimus 36520018280274912 **NOT PRECISE**
tertius decimus 1302947875804
quartus decimus 1300245641180
quintus decimus 1300253898716
sextus decimus 37774
septimus decimus 42759416798172
duodevicesimus 43016381192006637977600 **NOT PRECISE**
undevicesimus 1326703556626028691456 **NOT PRECISE**
vicesimus 351376069188572

Version without exploitation of floating point inaccuracy: 95 bytes
x=>1.618**(p=parseInt)("52d7i 6  he 8309jafc 41bg"[p(x.length+x[2],36)%158%29-4],36)*.4474+.5|0

Try it online!
b36_to_dec(x.length + x[2]) % 158 % 29 - 4
Hash Table
 Latin word           | Length | 3rd | Hash | Decimal | %158 | %29-4
----------------------+--------+-----+------+---------+------+-------
 primus               |      6 | i   | 6i   |     234 |   76 |    14
 secundus             |      8 | c   | 8c   |     300 |  142 |    22
 tertius              |      7 | r   | 7r   |     279 |  121 |     1
 quartus              |      7 | a   | 7a   |     262 |  104 |    13
 quintus              |      7 | i   | 7i   |     270 |  112 |    21
 sextus               |      6 | x   | 6x   |     249 |   91 |     0
 septimus             |      8 | p   | 8p   |     313 |  155 |     6
 octavus              |      7 | t   | 7t   |     281 |  123 |     3
 nonus                |      5 | n   | 5n   |     203 |   45 |    12
 decimus              |      7 | c   | 7c   |     264 |  106 |    15
 undecimus            |      9 | d   | 9d   |     337 |   21 |    17
 duodecimus           |     10 | o   | 10o  |    1320 |   56 |    23
 tertius decimus      |     15 | r   | 15r  |    1503 |   81 |    19
 quartus decimus      |     15 | a   | 15a  |    1486 |   64 |     2
 quintus decimus      |     15 | i   | 15i  |    1494 |   72 |    10
 sextus decimus       |     14 | x   | 14x  |    1473 |   51 |    18
 septimus decimus     |     16 | p   | 16p  |    1537 |  115 |    24
 duodevicesimus       |     14 | o   | 14o  |    1464 |   42 |     9
 undevicesimus        |     13 | d   | 13d  |    1417 |  153 |     4
 vicesimus            |      9 | c   | 9c   |     336 |   20 |    16


text:
Construct a line graph / conjugate graph
Introduction
Given an undirected graph G, we can construct a graph L(G) (called the line graph or conjugate graph) that represents the connections between edges in G. This is done by creating a new vertex in L(G) for every edge in G and connecting these vertices if the edges they represent have a vertex in common.
Here's an example from Wikipedia showing the construction of a line graph (in green).

As another example, take this graph G with vertices A, B, C, and D.
    A
    |
    |
B---C---D---E

We create a new vertex for each edge in G. In this case, the edge between A and C is represented by a new vertex called AC.
   AC

 BC  CD  DE

And connect vertices when the edges they represent have a vertex in common. In this case, the edges from A to C and from B to C have vertex C in common, so vertices AC and BC are connected.
   AC
  /  \
 BC--CD--DE

This new graph is the line graph of G!
See Wikipedia for more information.
Challenge
Given the adjacency list for a graph G, your program should print or return the adjacency list for the line graph L(G). This is code-golf, so the answer with the fewest bytes wins!
Input
A list of pairs of strings representing the the edges of G. Each pair describes the vertices that are connected by that edge.

Each pair (X,Y) is guaranteed to be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).

For example:
[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")]
[("D","E"),("C","D"),("B","C"),("A","C")]

Output
A list of pairs of strings representing the the edges of L(G). Each pair describes the vertices that are connected by that edge.

Each pair (X,Y) must be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).
For any edge (X,Y) in G, the vertex it creates in L(G) must be named XY (the names are concatenated together in same order that they're specified in the input).

For example:
[("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]
[("DE","CD"),("CD","CB"),("CD","CA"),("BC","AB")]

Test Cases
[] -> []

[("0","1")] -> []

[("0","1"),("1","2")] -> [("01","12")]

[("a","b"),("b","c"),("c","a")] -> [("ab","bc"),("bc","ca"),("ca","ab")]

[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")] -> [("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]

I don't see anything in the question ruling out an input like [("1","23"),("23","4"),("12","3"),("3","4")], for which the output should presumably be [("123","234"),("123","34")], which cannot be correctly interpreted. I think the only way to fix this is to edit in a guarantee that the input will never contain such ambiguities, but if this question had been posted in the sandbox then I would have suggested being less prescriptive about the naming of vertices in the output.

Further to Peter Taylor's comment, can we assume that the vertex names are all 1-character long in the input?

K (ngn/k), 45 39 33 29 30 35 and five years later: 31 bytes
(*'<:')#(3=#'?',/')#+{x@!2##x}@

Try it online!
{ }@ apply a function with implicit argument x
#x length
2# repeat twice
!2##x pairs of indices in x (the columns of a 2 by #x matrix)
x@ index into x
+ transpose
( )# filter
(3=#'?',/')# filter only those pairs whose concatenation (,/) has a count (#) of exactly 3 unique (?) elements
This removes edges like ("ab";"ab") and ("ab";"cd") from the list.
(*'>:')# filter only those pairs whose sort-descending permutation (>) starts with (*) a 1 (non-0 is boolean true)
In our case, the sort-descending permutation could be 0 1 or 1 0.

Brachylog, 13 bytes
{⊇Ċ.c¬≠∧}ᶠcᵐ²

Try it online!
With all test cases
(-1 byte replacing l₂ with Ċ, thanks to @Fatalize.)
{⊇Ċ.c¬≠∧}ᶠcᵐ²   Full code
{       }ᶠ      Find all outputs of this predicate:
 ⊇Ċ.             A two-element subset of the input
    c            which when its subarrays are concatenated
     ¬≠          does not have all different elements
                 (i.e. some element is repeated)
       ∧         (no further constraint on output)
          cᵐ²   Join vertex names in each subsubarray in that result

You can use the constrained variable Ċ (couple) instead of l₂ to save one byte.

Ruby, 51 bytes
->a{a.combination(2){|x,y|p [x*'',y*'']if(x&y)[0]}}

Try it online!
For each combination of two edges, if they have a vertex in common (i.e. if the first element of their intersection is non-nil), print an array containing the two edges to STDOUT.

Jelly, 5 bytes
Œcf/Ƈ

Try it online!

How are f and Ƈ used in Jelly? If I read it in the docs, both are filters. f is "Filter; remove the elements from x that are not in y." and Ƈ is "Filter (alias for Ðf). Keep all items that satisfy a condition.". Are they always used together? Is the Ƈ used to close the filter f? As in, is f...Ƈ similar to ʒ...} in 05AB1E? Or has the / ("Reduce or n-wise reduce.") have something to do with it? Just trying to understand the code, and I'm confused by the two different filter commands (and how both are used here). :)

@KevinCruijssen No, f and Ƈ are two completely separate things. You can think of f as intersection (given two lists, it returns their common elements) and Ƈ is like ʒ in 05AB1E. In short: Œc returns all possible combinations of two elements from the list, then Ƈ only keeps those that satisfy the link (i.e. Jelly function) f/, which returns the intersection of the two items. But f is a dyad (two-argument function) and we need to apply it on a two-element list instead, so we have to use /, reduce.

Ah ok, that makes a lot more sense. I guess the term 'filter' for f in the docs, although correct, mainly confused me with the actual filter Ƈ being used. Your explanation of "given two lists, return their common elements" made it all clear. And I indeed had the feeling the / was used to convert Jelly's data somehow. Actually, I now see the section 6.6 Reducing in the Tutorial on the Jelly wiki that explains how it pops a dyad and pushes a reduced monad (basically 2 arguments vs a list of pairs as argument). Thanks, all clear now!

JavaScript (Firefox 30-57), 77 bytes
a=>[for(x of a=a.map(x=>x.join``))for(y of a)if(x<y&&x.match(`[${y}]`))[x,y]]

Assumes all inputs are single letters (well, any single character other than ^ and ]).

What makes Firefox 30-57 special for this answer?

@Night2 The array comprehension syntax was only supported in those versions of Firefox.

C (gcc), 173 bytes
Input i and output o are flat, null-terminated arrays. Output names can be up to 998 characters long before this will break.
#define M(x)o[n]=malloc(999),sprintf(o[n++],"%s%s",x[0],x[1])
f(i,o,j,n,m)char**i,**j,**o;{for(n=0;*i;i+=2)for(j=i;*(j+=2);)for(m=4;m--;)strcmp(i[m/2],j[m%2])||(M(i),M(j));}

Try it online!

163 bytes

MATL, 13 bytes
2XN!"@Y:X&n?@

Try it online!
Not as bad as I expected given cell array input. Basically the same idea as @Doorknob's Ruby answer.
2XN   % Get all combinations of 2 elements from the input
!     % Transpose
"     % Iterate over the columns (combinations)
@     % Push the current combination of edges
Y:    % Split it out as two separate vectors
X&n   % Get the number of intersecting elements between them
?@    % If that's non-zero, push the current combination on stack
      % Implicit loop end, valid combinations collect on the stack
      %  and are implicitly output at the end

Mathematica 23 bytes
EdgeList[LineGraph[#]]&

Example:  g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 2 <-> 4 }]

EdgeList@LineGraph[g]

(*
{2 <-> 1, 3 <-> 2, 4 <-> 1, 4 <-> 2, 4 <-> 3}
*)

Python 2, 109 bytes
lambda a:[(s,t)for Q in[[''.join(p)for p in a if x in p]for x in set(sum(a,()))]for s in Q for t in Q if s<t]

Try it online!
For each node x (discovered by making a set from the flattened list of edges), make a list of the pairs p that have x as a member; then, for each of those lists Q, find the unique, distinct pairings within Q (uniqueness/distinction is enforced via if s<t).

Scala, 145 bytes
Modified from @Doorknob's Ruby answer.

Golfed version. Try it online!
def f(a:Seq[Seq[String]])=a.combinations(2).foreach{case List(x,y)=>if(x.intersect(y).nonEmpty)println(s"[${x.mkString("")},${y.mkString("")}]")}

Ungolfed version. Try it online!
object Main {
  def main(args: Array[String]): Unit = {
    val f: List[List[String]] => Unit = (a: List[List[String]]) => {
      a.combinations(2).foreach { case List(x, y) =>
        if (x.intersect(y).nonEmpty) println(s"[${x.mkString("")}, ${y.mkString("")}]")
      }
    }

    val inputList: List[List[List[String]]] = List(
      List(),
      List(List("0", "1")),
      List(List("0", "1"), List("1", "2")),
      List(List("a", "b"), List("b", "c"), List("c", "a")),
      List(List("1", "2"), List("1", "3"), List("1", "4"), List("2", "5"), List("3", "4"), List("4", "5"))
    )

    inputList.foreach { arr =>
      println(s"Input: $arr")
      println("Output:")
      f(arr)
      println()
    }
  }
}

Nekomata, 8 bytes
S:đ∩z¿ᵐj

Attempt This Online!
A port of @Sundar R's Brachylog answer
S:đ∩z¿ᵐj
S           Find a subset of the input
 :   ¿      Check that:
  đ             the subset has exactly two elements
   ∩            and the intersection of the two elements
    z           has exactly one element
      ᵐj    Join each element of the subset

Nekomata will find all solutions, which are all the edges of the edge graph.

Wolfram Language 64 53 bytes
""<>#&/@#&/@Select[#~Subsets~{2},IntersectingQ@@#&]&

Finds all the input list's Subsets of length 2, Select those in which the nodes of one pair intersect with the nodes of another pair (indicating that the pairs share a node), and StringJoin the nodes for all selected pairs.
The code is especially difficult to read because it employs 4 nested pure (aka "anonymous") functions.
The code uses braces, "{}", as list delimiters, as is customary in Wolfram Language.
1 byte saved thanks to Mr. Xcoder.

Example
""<>#&/@#&/@Select[#~Subsets~{2},IntersectingQ@@#&]&[{{"1","2"},{"1","3"},{"1","4"},{"2","5"},{"3","4"},{"4","5"}}]

(*{{"12", "13"}, {"12", "14"}, {"12", "25"}, {"13", "14"}, {"13", "34"}, {"14", "34"}, {"14", "45"}, {"25", "45"}, {"34", "45"}}*)

Your current is actually 65 bytes, not 64. However, you can golf 1 byte with Select[#~Subsets~{2},IntersectingQ@@#&]/.{a_,b_}:>{""<>a,""<>b}& – Try it online!

Pyth, 7 bytes
@F#.cQ2

Try it here!
If joining is necessary, 10 bytes
sMM@F#.cQ2

Try it here!

Your output does not have the required form.  You need to string join the nodes.

@DavidC I don't see why that would be needed and I cannot identify any portion of the challenge spefication that requires that, but I have added a version that joins them.

Joining was used in all of the test cases.  In my case, joining cost 9 bytes.  You were able to do it with just 3 additional bytes.  Impressive!

C# 233 bytes
static void c(List<(string a,string b)>i,List<(string,string)>o){for(int m=0;m<i.Count;m++){for(int n=m+1;n<i.Count;n++){if((i[n].a+i[n].b).Contains(i[m].a)||(i[n].a+i[n].b).Contains(i[m].b)){o.Add((i[m].a+i[m].b,i[n].a+i[n].b));}}}}

Example
using System;
using System.Collections.Generic;

namespace conjugateGraphGolf
{
    class Program
    {
        static void Main()
        {
            List<(string a, string b)>[] inputs = new List<(string, string)>[]
            {
                new List<(string, string)>(),
                new List<(string, string)>() {("0", "1")},
                new List<(string, string)>() {("0", "1"),("1", "2")},
                new List<(string, string)>() {("a","b"),("b","c"),("c","a")},
                new List<(string, string)>() {("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")}
            };

            List<(string, string)> output = new List<(string, string)>();

            for(int i = 0; i < inputs.Length; i++)
            {
                output.Clear();
                c(inputs[i], output);

                WriteList(inputs[i]);
                Console.Write(" -> ");
                WriteList(output);
                Console.Write("\r\n\r\n");
            }

            Console.ReadKey(true);
        }

        static void c(List<(string a,string b)>i,List<(string,string)>o){for(int m=0;m<i.Count;m++){for(int n=m+1;n<i.Count;n++){if((i[n].a+i[n].b).Contains(i[m].a)||(i[n].a+i[n].b).Contains(i[m].b)){o.Add((i[m].a+i[m].b,i[n].a+i[n].b));}}}}

        public static void WriteList(List<(string a, string b)> list)
        {
            Console.Write("[");
            for(int i = 0; i < list.Count; i++)
            {
                Console.Write($"(\"{list[i].a}\",\"{list[i].b}\"){(i == list.Count - 1 ? "" : ",")}");
            }
            Console.Write("]");
        }
    }
}